Leetcode Link:
题目
给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
- 字符
'L'和'R'表示片段，其中片段'L'只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段'R'只有在其右侧直接存在一个 空位 时才能向 右 移动。 - 字符
'_'表示可以被 任意'L'或'R'片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
解法一
思路：
这题似乎看上去比较复杂，但是实际上想清楚了还是比较简单，根据题意，我们知道 target 和 start 中 L 和 R 的相对位置必需是一样的，当 R 和 L 相邻时，两者不能跨过对方。
并且注意到 R 只能向右移动，L 只能向左移动，因此满足条件的 target 中的 R 必需全部在 start 中 R 的右边，或者同样的位置才可以；L 同理。
这里我们可以用栈来判断，idx从大变小，遇到target中R入栈，遇到start中的R出栈，这一过程必需完美结束才可以，一旦出栈时遇到栈空，则必不满足条件。
题解：
class Solution:
def canChange(self, start: str, target: str) -> bool:
# 判断相对位置是否一样
tmp1 = start.replace("_", "")
tmp2 = target.replace("_", "")
if tmp1 != tmp2:
return False
# 检查target的所有R是不是在start的右边或者同等位置，可以用栈来检查
r = len(target)-1
stack = collections.deque()
while(r>=0):
if target[r] == 'R':
stack.append('R')
if start[r] == 'R' and len(stack)!=0:
stack.popleft()
elif start[r] == 'R' and len(stack)==0:
return False
r -= 1
# 检查target的所有L是不是在start的左边或者同等位置，可以用栈来检查
l = 0
while(l<len(target)):
if target[l] == 'L':
stack.append('L')
if start[l] == 'L' and len(stack)!=0:
stack.popleft()
elif start[l] == 'L' and len(stack)==0:
return False
l += 1
return True