难度：★★★☆☆
类型：数组
方法：逻辑
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
题目
在一个由 '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解决方案，请移步力扣中等题解析
