LeetCode 777. 在 LR 字符串中交换相邻字符
目录
题目描述
题意分析
给定两个等长的字符串
start和end，它们只由L、R、X三种字符组成。允许的操作只有两种：把子串XL替换成LX，或者把子串RX替换成XR。问能否经过任意多次操作把start变成end。这两条替换规则要翻译成物理含义才好用。
XL → LX意味着一个L可以与它左边紧邻的X交换，也就是L只能向左移动；RX → XR意味着一个R可以与它右边紧邻的X交换，也就是R只能向右移动。X本身没有独立的移动能力，它只是被L和R挤开的空位。把规则从「字符串替换」重述成「棋子在轨道上单向滑动」，整道题的结构立刻清晰。由此推出第一条不变量：
L和R永远无法互相穿越。L只能与X换位、R也只能与X换位，任何一次操作都不会让一个L跨过一个R，也不会让两个同类互换先后。所以去掉所有X之后，剩下的字符序列在整个变换过程中恒定不变。这是判定的第一道关口：两串去X后的序列必须完全相同，否则直接无解。第二条不变量来自移动方向的单向性：每个
L在end中的位置必须不大于它在start中的位置（只能左移），每个R在end中的位置必须不小于它在start中的位置（只能右移）。这里的「每个」是按去X序列一一对应的第 $k$ 个字符来说的。反过来，这两条必要条件也是充分的——只要相对顺序一致且每个棋子的移动方向合法，就一定能构造出一串操作把
start变成end（因为棋子之间不会互相阻挡：需要左移的L从左往右依次处理，需要右移的R从右往左依次处理，中间的X总是够用）。所以判定可以只检查这两条。约束是 $1 \le n \le 10^4$，两串等长。规模不大，但也足以排除「枚举所有操作序列做搜索」的方向——状态空间是指数级的。$O(n)$ 的一次扫描是自然目标。
边界方面：两串完全相同时显然可行；一串全是
X而另一串含有非X字符时不可行（去X序列长度不同）；某一侧的非X字符先耗尽而另一侧还有剩余，同样不可行。这三种情况都要被同一套指针逻辑覆盖。
解法：双指针匹配非 X 字符
核心思路
暴力思路是把字符串当作状态做广度优先搜索，每一步枚举所有可执行的替换。$n = 10^4$ 时状态数是天文数字，完全不可行。瓶颈很明确：我们在模拟过程，而实际上只需要验证两个不变量——过程本身是可构造的，不必真的走一遍。
于是转向判定。要同时验证「去
X序列相同」和「每个字符的位移方向合法」，最省事的办法是用两个指针分别在两串上跳过X，逐个配对非X字符。这样一次扫描就能同时拿到两份信息：配对上的字符是否相同（顺序一致性），以及它们各自的下标（位移方向）。显式写下不变量：任意时刻，指针 $i$ 与 $j$ 分别指向
start与end中第 $k$ 个非X字符（$k$ 为已配对的个数），且前 $k-1$ 对字符已经通过了「字符相同」与「移动方向合法」两项检查。每一轮做三件事：
- 对齐：让 $i$ 向右跳过
start中连续的X，让 $j$ 向右跳过end中连续的X。跳完之后，两个指针要么指向各自的第 $k$ 个非X字符，要么已经越过末尾。- 终止判定：如果两个指针都到了末尾，说明所有非
X字符都成功配对，返回真；如果只有一个到了末尾，说明两串的非X字符个数不同，去X序列必然不同，返回假。这两条判断的顺序不能交换——先判「都到末尾」才能正确接受合法输入。- 配对检查：先比较 $start[i]$ 与 $end[j]$ 是否相同，不同则去
X序列不同，返回假。相同则按字符类型检查位移方向：若是L，要求 $i \ge j$（它在end中的位置不能比在start中更靠右），所以 $i < j$ 时返回假；若是R，要求 $i \le j$，所以 $i > j$ 时返回假。三件事都通过后，两个指针各前进一步，进入下一轮。
这里最容易想歪的一点是方向判断的不等号。记住物理含义就不会错：
L向左走，所以它的终点下标只能更小或相等，即 $j \le i$；R向右走，终点下标只能更大或相等，即 $j \ge i$。取等是允许的——一个字符完全可以原地不动。外层循环的条件写成「$i < n$ 或 $j < n$」而不是「且」，是为了让「一侧先耗尽」这种情况也能进入循环体，被里面的终止判定捕获并返回假。如果写成「且」，一侧耗尽时循环直接退出并返回真，漏掉了非
X字符个数不等的情形。
解题步骤
- 第一步，令 $i = j = 0$，进入循环，条件是 $i < n$ 或 $j < n$。 为什么用「或」：需要让「$i$ 已到末尾但 $j$ 还没」这种不合法情形也进入循环体接受检查。用「且」会让这类输入直接跳出并返回真，漏判。
- 第二步，让 $i$ 跳过
start中的连续X，让 $j$ 跳过end中的连续X。 为什么可以无条件跳过：X只是空位，它的具体位置由L和R的落点唯一决定，不携带独立信息。跳过X之后剩下的比较，正是「去X序列」的逐位比较。- 第三步，若 $i$ 与 $j$ 都等于 $n$，返回真。 为什么这是成功的唯一出口：两串的非
X字符同时耗尽，说明个数相同、逐位相同、方向全部合法，三项条件齐备。- 第四步，若 $i$ 与 $j$ 中只有一个等于 $n$，返回假。 为什么必须放在第三步之后：先判「都到末尾」再判「只有一个到末尾」，顺序反了会把合法输入误判为失败。
- 第五步，比较 $start[i]$ 与 $end[j]$，不同则返回假。 为什么这一步就等价于「去
X序列相同」：两个指针始终指向各自的第 $k$ 个非X字符，逐位比较即是序列比较，无需真的构造出两个新字符串。- 第六步，若字符是
L且 $i < j$，返回假。 为什么：L只能左移，它在end中的下标 $j$ 不能大于在start中的下标 $i$。$i < j$ 意味着这个L需要向右移动，而没有任何操作能做到。- 第七步，若字符是
R且 $i > j$，返回假。 为什么：对称地，R只能右移，$i > j$ 意味着它需要向左移动，同样不可能。- 第八步，两个指针各加一，进入下一轮。 为什么必须同时加一：它们是配对推进的，任何一方单独前进都会打乱「第 $k$ 个对第 $k$ 个」的对应关系。
- 第九步，循环因两侧都耗尽而自然退出时返回真。 实践中这条路径通常不会被走到（第三步已经返回），但保留它能让函数在逻辑上完整。
以
start = "RXXLRXRXL"、end = "XRLXXRRLX"走一遍（$n = 9$）。两串的下标与字符对照：
start是0:R 1:X 2:X 3:L 4:R 5:X 6:R 7:X 8:L，end是0:X 1:R 2:L 3:X 4:X 5:R 6:R 7:L 8:X。先手算预期：start去X得RLRRL，end去X也得RLRRL，顺序一致，接下来只需逐个检查方向。第 1 轮：$i = 0$ 处是
R，不需跳过；$j = 0$ 处是X，跳到 $j = 1$（字符R）。两者都未越界。字符都是R，相同。检查方向：R要求 $i \le j$，这里 $0 \le 1$ 成立——这个R从下标 0 右移到下标 1，合法。指针推进到 $i = 1$、$j = 2$。第 2 轮：$i = 1$ 与 $i = 2$ 都是
X，跳到 $i = 3$（字符L）；$j = 2$ 处是L，无需跳。字符都是L，相同。检查方向：L要求 $i \ge j$，这里 $3 \ge 2$ 成立——这个L从下标 3 左移到下标 2，合法。推进到 $i = 4$、$j = 3$。第 3 轮：$i = 4$ 处是
R，无需跳；$j = 3$、$j = 4$ 都是X，跳到 $j = 5$（字符R）。字符都是R。方向检查 $4 \le 5$ 成立，右移一格，合法。推进到 $i = 5$、$j = 6$。第 4 轮：$i = 5$ 是
X，跳到 $i = 6$（字符R）；$j = 6$ 处是R，无需跳。字符相同。方向检查 $6 \le 6$ 成立——取等，说明这个R原地不动，这正是为什么不等号必须允许相等。推进到 $i = 7$、$j = 7$。第 5 轮：$i = 7$ 是
X，跳到 $i = 8$（字符L）；$j = 7$ 处是L。字符相同。方向检查 $8 \ge 7$ 成立，左移一格，合法。推进到 $i = 9$、$j = 8$。第 6 轮：循环条件「$i < 9$ 或 $j < 9$」中，$j = 8 < 9$ 成立，进入循环体。$i$ 已是 9，跳
X的内层循环不执行；$j = 8$ 处是X，跳到 $j = 9$。此时 $i = 9$ 且 $j = 9$，返回真。这最后一轮很关键：
end末尾还剩一个X没被消费，若外层循环条件写成「且」，第 5 轮结束后 $i = 9$ 就直接退出了——本例仍返回真所以不暴露，但换成start = "X"、end = "L"就会出问题：$i$ 跳过X后变成 1（越界），$j = 0$ 指向L；用「且」时循环根本不会进入，返回真，而正确答案是假。用「或」则进入循环体，被「只有一个到末尾」的判断拦下，正确返回假。再补两个失败用例。
start = "LX"、end = "XL"：第 1 轮 $i = 0$ 指向L，$j$ 跳过X到 1 指向L，字符相同但 $i = 0 < j = 1$，这个L需要右移，返回假。start = "XXRXXLXXXX"、end = "XXXXRXXLXX"：第 1 轮R从下标 2 到下标 4，$2 \le 4$ 合法；第 2 轮L从下标 5 到下标 7，$5 < 7$ 意味着要右移，返回假。
代码实现
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)$。两个指针各自单调向右移动，永不回退，所以 $i$ 与 $j$ 加起来最多走 $2n$ 步。内层跳
X的循环虽然嵌套在外层里，但它推进的正是同一个指针，总步数受同一个上界约束——这是典型的双指针均摊分析，不能被嵌套的表象误导成 $O(n^2)$。- 空间复杂度：$O(1)$。只用了两个下标变量和两个临时字符。特别注意我们没有真的构造出两个「去
X后的字符串」——那样是 $O(n)$ 空间；靠指针跳过X就地比较，把空间压到了常数。
关键点总结
- 把替换规则翻译成物理运动，不变量自然浮现。
XL → LX读作「L只能左移」、RX → XR读作「R只能右移」之后，「相对顺序不变」和「位移方向单向」两条不变量几乎是显然的。凡是给出一组局部替换规则的题，第一步都应该问：这些规则保持了什么量不变？- 可达性判定往往等价于「若干个不变量同时成立」。不必模拟操作序列，只需找齐必要条件并论证它们也是充分的。本题的两条条件合起来既必要又充分，所以一次线性扫描就能定论。
- 「跳过无关字符后逐位比较」用双指针实现，不要真的构造新串。这个手法在比较含退格的字符串、判断子序列、长按键入等题里反复出现，共同点是：某类字符不携带独立信息，可以在扫描时就地忽略。
- 循环条件用「或」还是「且」，取决于你想让哪些非法情形进入检查。这里必须用「或」，才能让「一侧先耗尽」被循环体内的判断捕获。写双指针时要专门想一想：两个指针不同步结束时，我的循环还能不能发现问题？
- 方向判断的不等号必须允许取等。字符原地不动是合法的，
L用 $i \ge j$、R用 $i \le j$。把等号漏掉会让所有「不需要移动的字符」被判为非法，几乎所有正例都会挂掉。- 面试视角：这题的全部分数都在「你能不能说出两条不变量」。开口先讲「
L只能左移、R只能右移，所以去掉X后的序列恒定」，再讲「每个字符的位移方向受限」，最后说明这两条既必要又充分——讲完之后代码只是十几行的直接翻译。面试官常见的追问是「为什么充分」，要能答出「棋子之间不会互相阻挡，按合适顺序逐个移动即可构造出操作序列」。另一个追问是「不用双指针行不行」，可以答：把两串各自压缩成「非X字符 + 其下标」的列表再逐项比较，逻辑等价但多花 $O(n)$ 空间，双指针是它的原地版本。
易错点总结
- 错误写法：外层循环条件写成
i < n && j < n。以start = "X"、end = "L"为例，$i$ 跳过X后越界，循环条件不成立直接退出并返回真，而正确答案是假（X无法变出一个L）。必须用「或」，让一侧耗尽的情形进入循环体接受检查。- 错误写法：
L的方向判断写成i > j返回假。以start = "XL"、end = "LX"为例，L从下标 1 左移到下标 0，$i = 1 > j = 0$ 会被误判为非法，返回假，而正确答案是真。方向搞反会让所有本该成功的左移全部失败。- 错误写法：
R的方向判断写成i < j返回假。以start = "RX"、end = "XR"为例，R从下标 0 右移到下标 1，$i = 0 < j = 1$ 被误判为非法，返回假，而正确答案是真。- 错误写法：方向判断漏掉取等，写成
L要求 $i > j$、R要求 $i < j$。以start = "L"、end = "L"为例，字符原地不动，$i = j = 0$ 两个条件都不满足，返回假，而正确答案是真。任何不需要移动的字符都会被这个 bug 判死。- 错误写法：先判「只有一个到末尾」再判「都到末尾」。以
start = "L"、end = "L"为例，第 2 轮时 $i = j = 1 = n$，若先执行if (i == n || j == n) return false，会直接返回假，而正确答案是真。两个判断的顺序不可交换。- 错误写法：只比较去
X后的序列是否相同，不检查位移方向。以start = "LX"、end = "XL"为例，两串去X后都是L，序列一致，会返回真；但这个L需要向右移动，实际不可能，正确答案是假。顺序一致只是必要条件之一。- 错误写法：只检查位移方向，不比较字符是否相同。以
start = "RL"、end = "LR"为例，第一对下标都是 0，按start的字符R检查 $0 \le 0$ 通过；第二对下标都是 1，按L检查 $1 \ge 1$ 通过，最终返回真，而两串去X后分别是RL与LR，顺序不同，正确答案是假。两项检查缺一不可。- 错误写法：跳过
X的内层循环忘记边界判断，写成while (start.charAt(i) == 'X') i++。以start = "XX"、end = "XX"为例，$i$ 一路加到 2 之后继续访问charAt(2)，Java 抛字符串越界异常，Go 直接 panic。跳过循环必须同时判 $i < n$。- 错误写法：只推进一个指针，比如比较通过后只写
i++。以start = "RL"、end = "RL"为例，第一对匹配后 $i = 1$、$j = 0$，第二轮拿start[1] = 'L'与end[0] = 'R'比较，字符不同返回假，而正确答案是真。两个指针必须成对推进。- 错误写法：先构造出两个去
X的字符串再比较，但丢掉了原下标。以start = "LX"、end = "XL"为例，压缩后两串都是L，比较结果相同而返回真，正确答案是假。位移方向的判断依赖原始下标，压缩时必须把下标一起记下来，否则信息丢失。- 错误写法：以为
X之间也需要一一对应。以start = "RXXLRXRXL"、end = "XRLXXRRLX"为例，两串中X的分布完全不同，但答案是真。X是被动的空位，它的位置由L、R的落点决定，绝不能参与配对。- 错误写法：用广度优先搜索模拟所有可能的替换。以 $n = 10^4$ 的输入为例，状态空间随长度指数增长，必然超时甚至内存耗尽。可达性判定题应优先寻找不变量，而不是模拟过程。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 844. 比较含退格的字符串 | 简单 | 同样是「跳过无效字符后逐位比较」，但退格要从右往左扫且需计数抵消 |
| 925. 长按键入 | 简单 | 双指针配对时允许一侧出现重复字符，推进规则不对称 |
| 392. 判断子序列 | 简单 | 只要求顺序包含而不要求完全一致，一个指针可以停留不动 |
| 283. 移动零 | 简单 | 把「空位」挤到末尾的原地双指针，是本题 X 作为空位这一视角的最简形态 |
| 1247. 交换字符使得字符串相同 | 中等 | 交换的是任意两处而非相邻，问题从可达性判定变成最少交换次数的贪心配对 |
| 1202. 交换字符串中的元素 | 中等 | 可交换关系构成连通分量，分量内可任意重排，考察的是「哪些不变量被打破了」 |
| 1657. 确定两个字符串是否接近 | 中等 | 同为「给定操作下的可达性判定」，不变量是字符集合与频次的多重集 |
| 125. 验证回文串 | 简单 | 双指针跳过非字母数字字符后比较，练习「忽略无关字符」的指针推进模板 |