难度：★★★☆☆
类型：数组
方法：逻辑

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

在一个由 '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'。

解答

解法1：回溯

有一个752密码锁的问题和它很像，我们首先可以用回溯的办法搜索整个可能的空间，如下：

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        seen = {start}
        stack = [start]

        while stack:
            current = stack.pop(0)
            if current == end:
                return True
            for index in range(len(start)):
                if current[index:index+2] == 'XL':
                    new = current[:index] + 'LX' + current[index + 2:]
                    if new not in seen:
                        stack.append(new)
                        seen.add(new)
                elif current[index:index+2] == 'RX':
                    new = current[:index] + 'XR' + current[index + 2:]
                    if new not in seen:
                        stack.append(new)
                        seen.add(new)
        return False

解法2：逻辑

但是计算开销是很大的，超过耗时需要。通过观察题目的要求，我们很容易发现这道题的一个特点，有必要理解一下题目中给出的字符串中三种字符的含义：
X：任意字符；
L：left的简写，如果它的左边与X相邻，可以交换位置，即该字母左移；
R：right的简写，如果它的右边与X相邻，可以交换位置，即该字母右移；

我们很容易发现，始态start和末态end两个字符串去掉X后，只剩下包含L和R的字符串，这两个字符串需要完全相同的，但是只有这个依据是不够的，start中的L需要通过左移得到end中对应的L，start中的R需要通过右移得到end中对应的R，因此另一个关键点是L对或者R对在start和end中的位置关系。

我们统计start和end中所有L和R的位置，并将它们用元组形式保存在列表中，始态和末态对应列表长度必须一致，并且L和R必须在列表中相应位置一一对应。接下来来就是判断下标的工作，如果在始态中的L的位置在末态中对应的L的位置的左边，这个L是无法通过左移到达末态的，同理，根据类似原理判断始态中R的位置与末态中相应的R的位置的关系。
如果一切满足，返回True即可。

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        start_id = []
        for i, c in enumerate(start):
            if c in ['L', 'R']:
                start_id.append((i, c))

        end_id = []
        for i, c in enumerate(end):
            if c in ['L', 'R']:
                end_id.append((i, c))

        if len(start_id) != len(end_id):
            return False

        for (i1, c1), (i2, c2) in zip(start_id, end_id):
            if c1 != c2:
                return False
            if c1 == c2 == 'L' and i1 < i2:
                return False
            if c1 == c2 == 'R' and i1 > i2:
                return False
        return True

这里是一个python三行代码精简版，更短更快：

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        start = [(i, c) for i, c in enumerate(start) if c in ["L", "R"]]
        end = [(i, c) for i, c in enumerate(end) if c in ["L", "R"]]
        return len(start) == len(end) and all(c1 == c2 == "L" and i1 >= i2 or c1 == c2 == "R" and i1 <= i2 for (i1, c1), (i2, c2) in zip(start, end))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析