难度: Medium
在一个由 '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
提示：
1 <= len(start) = len(end) <= 10000。start和end中的字符串仅限于'L', 'R'和'X'。运行时间: 33 ms
内存: 16.1 MB
class Solution:
def canTransform(self, start: str, end: str) -> bool:
i, j, n =0, 0, len(start)
while i < n or j < n:
while i < n and start[i] == 'X':
i += 1
while j < n and end[j] == 'X':
j += 1
if i == n or j == n:
return i == j
if start[i] != end[j]:
return False
if start[i] == 'L' and i < j:
return False
if start[i] == 'R' and i > j:
return False
i, j = i + 1, j + 1
return i == j
这个题解的思路是使用双指针 i 和 j 分别在 start 和 end 字符串上移动。当指针所指的字符为 'X' 时，指针就一直向右移动，直到遇到 'L' 或 'R'。然后比较两个指针所指的字符是否相同，如果不同则返回 False。接着判断对于 'L' 和 'R' 的相对位置关系，'L' 只能向左移动，'R' 只能向右移动，如果位置关系不满足则返回 False。最后当任一指针达到字符串尾部时，判断两个指针是否同时到达尾部，如果不是则返回 False，否则返回 True。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def canTransform(self, start: str, end: str) -> bool:
i, j, n = 0, 0, len(start)
while i < n or j < n:
# 跳过所有的 'X'
while i < n and start[i] == 'X':
i += 1
while j < n and end[j] == 'X':
j += 1
# 判断两个指针是否同时到达尾部
if i == n or j == n:
return i == j
# 判断两个指针所指字符是否相同
if start[i] != end[j]:
return False
# 判断 'L' 和 'R' 的相对位置关系
if start[i] == 'L' and i < j:
return False
if start[i] == 'R' and i > j:
return False
i, j = i + 1, j + 1
return i == j
在算法中，'X' 视为可以通过忽略的空位，而 'L' 和 'R' 是有明确移动限制的字符。'L' 只能向左移动，'R' 只能向右移动。因此，遇到 'L' 或 'R' 时需要停止跳过 'X' 是为了检查这两个字符是否能在对应的位置上匹配或是否能通过合法的移动达到目标位置。如果继续跳过，我们可能会错过 'L' 和 'R' 之间的相对位置关系，这是判断转换是否可能的关键。
这种判断依据是 'L' 和 'R' 的移动规则。根据题目设定，'L' 只能向左移动（即向字符串的起始方向移动），而 'R' 只能向右移动（即向字符串的结束方向移动）。因此，如果在 start 字符串中 'L' 的位置在 end 字符串中的对应 'L' 的位置的右边，表示这个 'L' 在 end 中已经向左移动了；反之，如果 'R' 在 start 中的位置比在 end 中的位置靠左，表示这个 'R' 在 end 中已经向右移动了。这是按照它们各自的移动规则进行判断的逻辑结果。
题解中通过双指针技术确保两个字符串中的非 'X' 字符完全一致。每次跳过 'X' 后，比较两个指针所指向的字符。如果这两个字符不同，则直接返回 False，这保证了只有当两个字符串中相同位置的非 'X' 字符相同时，算法才继续执行。如果某个指针到达字符串末尾而另一个没有，或者两个指针所指的非 'X' 字符不一致，都会被检测出来，因此不存在漏检的情况。
这种方法足够保证 start 可以通过规定的移动操作转换成 end。在循环中，已经确保了所有非 'X' 字符都能在合法的位置匹配，且字符间的相对位置满足移动规则。循环结束时，返回 i == j 的结果确保两个指针都同时达到各自字符串的末尾，这意味着除了 'X' 外，所有字符都已正确匹配，且没有多余的非 'X' 字符在任一字符串中。因此，这足以证明一个字符串可以通过规定的操作转换成另一个字符串。