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

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
字符串 双指针

题目描述

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

image-20260929104757075

题意分析

两个等长字符串只含 L、R、X，允许把 XL 变成 LX，或把 RX 变成 XR，判断能否从起始串得到目标串。可以把 X 看作空位：L 只能向左移，R 只能向右移，两个棋子不能直接交换。

解法：双指针匹配非 X 字符

核心思路

[!blue]

每次操作只交换一个棋子与空位，两个棋子永远不能越过彼此。因此去掉 X 后，两串的 L、R 序列必须完全相同，按出现次序匹配的两个字符才代表同一个棋子。

设某个棋子的起点下标为 i、目标下标为 j。L 只能左移，所以必须 i >= j；R 只能右移，所以必须 i <= j。相等表示不需要移动。这些方向条件与顺序条件都是必要的。

它们也足够：可以先从左到右把所有 L 移到目标位置。此前的 L 已经就位；此前的 R 的起点不晚于自身目标，而自身目标又在当前 L 的目标左侧，因此不会挡在当前移动区间中。再从右到左处理 R，右侧的 R 已就位，L 也已固定，保持的相对顺序保证这一段同样只有空位。于是所有棋子都能按允许方向到位。

实现时无需模拟这些交换，用两个指针分别跳过 X，逐一检查棋子类型和位置即可。若只剩一串还有棋子，数量或顺序不一致；若两边都耗尽，所有棋子都通过了检查，返回 true。

解题步骤

  1. 双指针跳过各自字符串中的 X。
  2. 若一方已结束，检查另一方是否也没有剩余棋子。
  3. 比较当前非 X 字符和对应位置的移动方向。
  4. 通过检查后同时推进，直到全部匹配。

代码实现

class Solution {
    public boolean canTransform(String start, String end) {
        int n = start.length();
        int i = 0;
        int j = 0;

        while (i < n || j < n) {
            while (i < n && start.charAt(i) == 'X') {
                i++;
            }

            while (j < n && end.charAt(j) == 'X') {
                j++;
            }

            if (i == n && j == n) {
                return true;
            }

            if (i == n || j == n) {
                return false;
            }

            char a = start.charAt(i);
            char b = end.charAt(j);

            if (a != b) {
                return false;
            }

            // 左移棋子的目标位置不能比起点更靠右。
            if (a == 'L' && i < j) {
                return false;
            }

            // 右移棋子的目标位置不能比起点更靠左。
            if (a == 'R' && i > j) {
                return false;
            }

            i++;
            j++;
        }

        return true;
    }
}

func canTransform(start string, end string) bool {
    n := len(start)
    i, j := 0, 0

    for i < n || j < n {
        for i < n && start[i] == 'X' {
            i++
        }
        for j < n && end[j] == 'X' {
            j++
        }

        if i == n && j == n {
            return true
        }
        if i == n || j == n {
            return false
        }

        if start[i] != end[j] {
            return false
        }
        // 左移棋子的目标位置不能比起点更靠右。
        if start[i] == 'L' && i < j {
            return false
        }
        // 右移棋子的目标位置不能比起点更靠左。
        if start[i] == 'R' && i > j {
            return false
        }
        i++
        j++
    }

    return true
}

复杂度分析

  • 时间复杂度：$O(n)$，两个指针各自只向前移动。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 顺序约束与方向约束缺一不可。
  • X 表示可移动的空位，不需要逐步模拟每次交换。
  • 结束时两边必须同时耗尽非 X 字符。

易错点总结

[!yellow]

  • 只比较 L、R 总数：无法发现相对顺序变化。
  • 把 L 和 R 的位置不等式写反：会接受禁止方向的移动。
  • 只要任一指针结束就返回 true：另一串可能还有未匹配棋子。
  • 要求 X 的下标保持不变：空位本来就会随操作移动。
  • 外层只在两指针都未结束时继续：可能漏查另一串末尾剩余的棋子，应确认两边同时耗尽。

相似题目

题目 难度 关联与区别
2337. 移动片段得到字符串 中等 移动规则等价：L只能左移、R只能右移，空位符号不同；可复用去除空位后的次序与位置约束判定。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/31283409
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！