LeetCode 777

777. 在LR字符串中交换相邻字符

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时，返回True。

示例 :

输入: start = "RXXLRXRXL", end = "XRLXXRRLX"
输出: True
解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX</pre>

注意:

1 <= len(start) = len(end) <= 10000。
start和end中的字符串仅限于'L', 'R'和'X'。

通过次数2,186

提交次数6,849

"状态转换"类的问题,最重要的想法就是:在转换中,哪些东西是不变的?就说这个题,它其中不变的东西就是:L和R的相对顺序是不变的!!!

首先,我们要判断一下L和R的相对顺序在start和end里面是不是一样就行;

然后考虑L只能向左走,R只能向右走;假设所有的L在start里面的位置,在end里面的位置为,只需要满足就行了.对R也同样如此

然后一个双指针算法就可以了:

class Solution {
public:
 bool canTransform(string start, string end) {
   int t1=0,t2=0;

   while(t1<start.length() && t2<end.length()){
   while(start[t1]=='X'&&t1<start.length())t1++;
   while(end[t2]=='X'&& t2<end.length())t2++;
   if(start[t1]!=end[t2]||(start[t1]=='L'&&t1<t2)||(start[t1]=='R'&&t1>t2)){
       return false;
     }
     t1++;
     t2++;
   }

   return true;
 }
};