Skip to content

Latest commit

 

History

History
133 lines (98 loc) · 3.99 KB

777._Swap_Adjacent_in_LR_String.md

File metadata and controls

133 lines (98 loc) · 3.99 KB
Raw

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

难度: 中等

刷题内容

原题连接

内容描述


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