# 777. Swap Adjacent in LR String 在LR字符串中交换相邻字符

## 刷题内容



RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

1 <= len(start) = len(end) <= 10000。
start和end中的字符串仅限于'L', 'R'和'X'。


## 解题方案

1. dp[i-1] == False
2. 如果start[i] == end[i]，那么dp[i] = False
3. 如果start[i] != end[i]，那么只有当最后两个字符可以转换且dp[i-2] == True的情况下dp[i]才为True

class Solution(object):
def canTransform(self, start, end):
"""
:type start: str
:type end: str
:rtype: bool
"""
if not start or len(start) == 0:
return True
if len(start) == 1:
return False

dp = [False for i in range(len(start))]
if start[:2] == 'XL' and end[:2] == 'LX' or start[:2] == 'RX' and end[:2] == 'XR' or start[:2] == end[:2]:
dp[1] = True
for i in range(2, len(dp)):
if dp[i-1]:
if start[i] == end[i]:
dp[i] = True
else:
if start[i] == 'L' and start[i-1] == 'X' and end[i] == 'X' and end[i-1] == 'L' and dp[i-2]:
dp[i] = True
if start[i] == 'X' and start[i-1] == 'R' and end[i] == 'R' and end[i-1] == 'X' and dp[i-2]:
dp[i] = True
return dp[-1]


class Solution(object):
def canTransform(self, start, end):
"""
:type start: str
:type end: str
:rtype: bool
"""
if not start or len(start) == 0 or start == end:
return True
if len(start) == 1:
return False

xl, rx = [], []
for i in range(len(start)):
if start[i] == end[i]:
continue
elif start[i] == 'X' and end[i] == 'L':
xl.append('L')
elif start[i] == 'L' and end[i] == 'X':
if not xl:
return False
xl.pop()
elif start[i] == 'R' and end[i] == 'X':
rx.append('R')
elif start[i] == 'X' and end[i] == 'R':
if not rx:
return False
rx.pop()
else:
return False
return not rx and not xl


apachecn/AiLearning