leetcode [777] 在LR字符串中交换相邻字符

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

在一个由 ‘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'。

思路来自题解:

原理：在start中，L只能向左移动，R只能向右移动，只有在遇到X的时候可以移动, 因此X相当于是个空格，遇到空格L可以向左移动，R可以向右移动，其他情况不能移动

判定start能否转为end,即

（1）都去除X后，start和end一致

（2）如果L配对成功还需满足 start的下标大于等于 end的下标

如果R配对成功还需满足 start的下标小于等于 end的下标

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        if len(start) != len(end) or Counter(start) != Counter(end): return False
        start_record = [(i, s) for i, s in enumerate(start) if s in 'RL']
        end_record = [(i, s) for i, s in enumerate(end) if s in 'RL']
        for (s_i, s_s), (e_i, e_s) in zip(start_record, end_record):
            if s_s != e_s:
                return False
            if s_s == 'L' and s_i < e_i:
                return False
            if s_s == 'R' and s_i > e_i:
                return False
        return True