『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

提示：

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

题解

【在LR字符串中交换相邻字符】中等模拟

模拟

题目所说的操作归纳一下就是：

L 只能越过 X 向左移动
R 只能越过 X 向右移动
L, R 不能越过 X 移动

简单来说就是

必要条件是如果忽略掉 X 则原串和目标串是一样的，即 LR 在原串和目标串的相对位置要相同
如果目标串中有一个 L, 那么原串中对应的 L 要在其右边且中间不能有 R，即目标串的 L 要在原串对应 L 的左边
如果目标串中有一个 R, 那么原串中对应的 R 要在其左边且中间不能有 L，即目标串的 R 要在原串对应 R 的右边

# Code language: Python
# 浅浅压缩一下~ 展开版见 P2
class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        return start.count('X') == end.count('X') and all(c1 == c2 and ((c1 == 'L' and j <= i) or (c1 == 'R' and j >= i)) for (i, c1), (j, c2) in zip(*map(lambda s: ((i, c) for i, c in enumerate(s) if c != 'X'), (start, end))))

# Code language: Python
class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        if start.count('X') != end.count('X'):
            return False
            
        def get(s):
            # 可以压缩为 yield from ((i, c) for i, c in enumerate(s) if c != 'X')
            for i, c in enumerate(s):
                if c != 'X':
                    yield i, c
        
        for (i, c1), (j, c2) in zip(get(start), get(end)):
            if c1 != c2:
                return False
            if c1 == 'L' and j > i:
                return False
            if c1 == 'R' and j < i:
                return False
        return True

// Code language: C++
class Solution {
public:
    bool canTransform(string start, string end) {
        int n = start.size();
        for (int i = 0, j = 0; i < n || j < n; ++i, ++j) {
            while (i < n && start[i] == 'X') ++i;
            while (j < n && end[j] == 'X') ++j;
            // 数量不一致
            if (i == n && j != n) return false;
            if (i != n && j == n) return false;
            if (i == n && j == n) return true;
            // 相对位置不一致
            if (start[i] != end[j]) return false;
            // 相对位置不匹配
            if (start[i] == 'L' && j > i) return false;
            if (start[i] == 'R' && j < i) return false;
        }
        return true;
    }
};

// Code language: Java
class Solution {
    public boolean canTransform(String start, String end) {
        int n = start.length();
        for (int i = 0, j = 0; i < n || j < n; ++i, ++j) {
            while (i < n && start.charAt(i) == 'X') ++i;
            while (j < n && end.charAt(j) == 'X') ++j;
            // 数量不一致
            if (i == n && j != n) return false;
            if (i != n && j == n) return false;
            if (i == n && j == n) return true;
            // 相对位置不一致
            if (start.charAt(i) != end.charAt(j)) return false;
            // 相对位置不匹配
            if (start.charAt(i) == 'L' && j > i) return false;
            if (start.charAt(i) == 'R' && j < i) return false;
        }
        return true;
    }
}

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』777 在LR字符串中交换相邻字符

题目

标签

题解

模拟