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

在一个由 ‘L’ , ‘R’ 和 ‘X’ 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个 “LX” 替换一个 “XL”，或者用一个 “XR” 替换一个 “RX”。现给定起始字符串 start 和结束字符串 result，请编写代码，当且仅当存在一系列移动操作使得 start 可以转换成 result 时， 返回 True。

示例 1：

输入：start = “RXXLRXRXL”, result = “XRLXXRRLX”
输出：true
解释：通过以下步骤我们可以将 start 转化为 result：
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
示例 2：

输入：start = “X”, result = “L”
输出：false

提示：

1 <= start.length <= 10${}^4$
start.length == result.length
start 和 result 都只包含 ‘L’, ‘R’ 或 ‘X’。

start和result去掉X字符后，剩余部分应该相同，L字符只能往左移动，R字符只能往右移动，双指针遍历，遇到不满足的条件返回false即可：

class Solution {
public:
    bool canTransform(string start, string result) {
        int n = start.size();

        int startIdx = 0;
        int resultIdx = 0;

        while (startIdx < n && resultIdx < n) {
            if (start[startIdx] == 'X') {
                ++startIdx;
                continue;
            }

            if (result[resultIdx] == 'X') {
                ++resultIdx;
                continue;
            }

            // 字符不同 ||
            // 字符是L，但向右移动 ||
            // 字符是R，但向左移动
            if (start[startIdx] != result[resultIdx] ||
                startIdx < resultIdx && start[startIdx] == 'L' ||
                startIdx > resultIdx && start[startIdx] == 'R') {
                return false;
            }

            ++startIdx;
            ++resultIdx;
        }
        // 以上循环结束时，可能start没有遍历完，或result没有遍历完

        // 如果start没有遍历完，且未遍历部分有非X字符，说明result里的非X字符少了
        while (startIdx < n) {
            if (start[startIdx] != 'X') {
                return false;
            }
            ++startIdx;
        }

        // 如果result没有遍历完，且未遍历部分有非X字符，说明result里的非X字符多了
        while (resultIdx < n) {
            if (result[resultIdx] != 'X') {
                return false;
            }
            ++resultIdx;
        }

        return true;
    }
};

如果start的长度为n，则此算法时间复杂度为O(n)，空间复杂度为O(1)。