LeetCode每日一题系列

题目：777. 在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

思路

题目意思为L可以一直沿着X往左移动，R可以一直沿着X往右移动，这里可以暂且不看X，我们只需比较start和end中L和R的相对位置是否相同即可
可以使用双指针法分别比较start和end的字符：

1. 若比较的两字符不相等直接返回False
2. 若字符为X，则start中下标必须大于等于end中的下标
3. 若字符为Y，则start中的下标必须小于等于end中的下标
4. 若比较某一字符串比较结束后，剩余某一字符串未遍历完，这时判断其后是否还有非X元素，如果有返回False，没有返回True

题解

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        n = len(start)
        i = j = 0
        while i < n and j < n:
            while i < n and start[i] == 'X':
                i += 1
            while j < n and end[j] == 'X':
                j += 1
            if i < n and j < n:
                if start[i] != end[j]:
                    return False
                c = start[i]
                if c == 'L' and i < j or c == 'R' and i > j:
                    return False
                i += 1
                j += 1
        while i < n:
            if start[i] != 'X':
                return False
            i += 1
        while j < n:
            if end[j] != 'X':
                return False
            j += 1
        return True