777. Swap Adjacent in LR String 在LR字符串中交换相邻字符
难度: 中等
刷题内容
原题连接
- https://leetcode.com/problems/swap-adjacent-in-lr-string
- https://leetcode-cn.com/problems/swap-adjacent-in-lr-string
内容描述
在一个由 '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
这道题就是一道坑比题，为什么我这么说，题目都说了是 Adjacent，然后XL换成LX的情况居然包括"XXXXXLXXXX"到"LXXXXXXXXX"， 你说这是 Adjacent吗，XL不相邻也可以换，我去nm的，不好意思爆粗口了。
先说一下XL必须相邻的解法吧，不能白费我功夫啊。
动态规划：dp[i]代表以index i结尾的字串是否能够被替换成功，首先dp[0]必须等于False吧，所以我们初始化全部设为False，然后把dp[1]也先判断好
那么很显然，对于dp[i]有下面的情况： 1. dp[i-1] == True - 如果start[i] == end[i]，那么dp[i] = True - 如果start[i] != end[i]，那么这里我们不做操作，因为初始化就是False
- dp[i-1] == False
- 如果start[i] == end[i]，那么dp[i] = False
- 如果start[i] != end[i]，那么只有当最后两个字符可以转换且dp[i-2] == True的情况下dp[i]才为True
最后返回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:
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]
接下来说一下XL可以不相邻的情况吧。
用rx 和 xl来存储出现了可以替换的可能性，即当start出现X或者R的时候,如果后面又开始出现结尾情况了，
我们就要pop一下对应的rx 和 xl中的一个
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
