题目链接：leetcode777

题面

题目大意

L只能左移，R只能右移，并且移动的时候旁边要有X帮助，问能否从当前移动到目标串。

解题思路

对于一个串，我们只需要考虑非『X』的元素，因为一旦其他两者复原则『X』也随之复原。

广搜

口胡一下，空间复杂度可能很高，并且时间复杂度也不低，可以用双向广搜优化一下。代码略。

双指针

我们从左到右扫，如果当前串和目标串最近的一个非「X」元素不相等，则一定不能复原，因为无论如何都会存在两个移动区间相交的点；如果只能目标串的元素在当前元素能移动的相反方向，则也不能复原，因为当前元素能移动的方向没有需要它的位置。注意可能某个指针会先扫完，如果另外一个指针还有非「X」元素则也不能复原，同上因为没有需要它的位置。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

实现代码

class Solution { public: bool canTransform(string start, string end) { int n = start.size(), m = end.size(); if (n != m) return false; int i = 0, j = 0; while(i<n && j<m) { while(i<n && start[i]=='X') i++; while(j<m && end[j]=='X') j++; if (i<n && j<n && (start[i]!=end[j] || i<j&&start[i]!='R' || i>j&&start[i]!='L')) return false; i++; j++; } while(i<n && start[i]=='X') i++; while(j<m && end[j]=='X') j++; return i==j; } };