LeetCode 833：字符串查找与替换的“同时替换”陷阱与解法

LeetCode 833这道题，我印象挺深。名字叫《字符串中的查找与替换》，听起来像一个基础题，实际上坑全埋在“查找与替换”这几个字里。很多人第一次写完会得到错误答案，不是不会匹配，而是把“同时替换”理解成了“按顺序逐个替换”。这篇文章咱们就从头把这个题捋一遍，从题面语义、两种主流写法，到索引越界、重叠冲突这些容易翻车的细节，最后再聊几个工程里的类似场景。无论你是刚开始刷题准备面试，还是已经刷了几百题想查漏补缺，这一篇应该都有点用。

1. 题目到底在说什么：别被“替换”两个字带偏

1.1 原题语义与示例

把题目翻译成大白话：给你一个原始字符串 s，三个长度相同的数组 indices、sources、targets。对于第 i 个操作，你去看 s 中从 indices[i] 开始的位置，是不是正好以 sources[i] 开头。是的话，就把这一段替换成 targets[i]；不是的话，这个操作直接忽略。所有操作都是基于原始的 s 来判定，最终一次性返回所有替换之后的结果。

“基于原始 s 判定”这一点，是理解整道题的钥匙。举个例子你就明白了。s = "abcd"，indices = [0, 2]，sources = ["ab", "cd"]，targets = ["X", "Y"]。第一个操作把 s[0..1] 的 "ab" 换成 "X"，第二个操作把 s[2..3] 的 "cd" 换成 "Y"，结果显然是 "XY"。

如果两个操作都命中，而且互不重叠，这个结果很直观。但题目不会只出这种简单情况，真正的麻烦在于替换之间可能重叠，可能索引相同，还可能替换结果的长短完全不一样。这些情况在题目描述里并没有展开强调，但测试用例里一定会有，所以先把基础语义吃透，后面的坑才能避开。

1.2 核心难点：同时替换不是顺序替换

如果直接写个循环，每匹配一个就执行一次s = s[:idx] + target + s[idx+len(src):]，大部分用例会挂。为什么？因为你的 s 已经变了，位置会错乱。比如还是 "abcd"，假设只有一个操作 indices=[2]，sources=["cd"]，你先替换成 "abY"，这没问题；但如果后面还有一个 indices=[1] 的操作，你原本希望它在原始 s 的 "b" 上判断，现在 s 变成 "abY"，"b" 的位置没变还好，一旦源串长度不一样，比如把 "ab" 换成 "X"，s 变成 "Xcd"，后面所有索引就全乱了。

所以必须把所有匹配判断先做完，再做替换输出。这就是“同时替换”的本质：判断阶段用原始 s，执行阶段统一拼新串。这个概念和现实里批量操作很像，比如你要给一篇文章的多个地方加粗，你会先找出所有需要加粗的位置，再统一排版，而不是每找一个就立刻改一次文档，否则原有的页码和偏移量全部失效。

用一个更直观的类比：全班同学排成一排，老师给每个人的任务是“如果我喊到你名字的时候，你手上拿的是红色纸，就换一张蓝纸”。所有同学必须先确认自己当前拿的是红色纸，再一起换。如果第一个人换了之后你才确认，你看到的可能是别人换过的纸，判断就不准了。LeetCode 833 要求的就是这种“先看现状、再统一动手”的模式。

2. 解法一：扫描标记法（推荐，最简单直观）

2.1 标记数组怎么设计

我推荐大家优先掌握的，是“扫描标记法”。思路分两步。

第一步，遍历所有操作，能匹配的就做上标记，不能匹配的直接丢弃。怎么标记？开一个长度为 n 的数组 match，初始值全部设为 -1。对于第 i 个操作，如果 s 从 indices[i] 开始确实匹配 sources[i]，就让 match[indices[i]] = i。这样，match 数组的每个位置要么是 -1，说明这个位置不需要替换；要么是某个操作编号，说明从这个位置开始要用对应的 target 替换。

第二步，从头到尾扫描 s。遇到 match[pos] == -1，就老老实实把 s[pos] 拼到结果里，pos++；遇到 match[pos] != -1，就把 targets[match[pos]] 拼接进去，然后 pos 直接跳过 sources[match[pos]] 的长度。这样扫一遍就能得到最终结果。

这种做法的好处是，判断阶段和执行阶段完全解耦。判断的时候用原始 s，执行的时候只看标记数组，不需要回看原始字符串，也不需要考虑替换之间的前后影响，逻辑非常干净。

2.2 完整代码（C++/Python）

C++ 代码：

class Solution { public: string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) { int n = s.size(), k = indices.size(); vector<int> match(n, -1); for (int i = 0; i < k; i++) { int idx = indices[i]; // 先确认不会越界，再确认真的匹配 if (match[idx] == -1 && idx + sources[i].size() <= n && s.compare(idx, sources[i].size(), sources[i]) == 0) { match[idx] = i; } } string ans; int i = 0; while (i < n) { if (match[i] != -1) { ans += targets[match[i]]; i += sources[match[i]].size(); } else { ans += s[i]; i++; } } return ans; } };

Python 版本也很简洁：

class Solution: def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str: n = len(s) match = [-1] * n for i, (idx, src) in enumerate(zip(indices, sources)): if idx + len(src) <= n and s.startswith(src, idx): if match[idx] == -1: match[idx] = i ans = [] i = 0 while i < n: if match[i] != -1: ans.append(targets[match[i]]) i += len(sources[match[i]]) else: ans.append(s[i]) i += 1 return "".join(ans)

2.3 复杂度分析

时间复杂度：第一步遍历 k 个操作，每个操作做一次字符串比较，如果源串平均长度是 L，比较代价是 O(L)，所以预标记阶段是 O(kL)。第二步扫描，每个字符最多被拼接一次，每个被匹配的源串一次性跳过，所以扫描阶段是 O(n + 总结果长度)。把结果串也算进去，整体大概是 O(n + kL + 结果长度)。对于 n、k 最大不超过 1000 的题目约束，这个复杂度非常舒服。

空间复杂度：match 数组 O(n)，ans 字符串 O(结果长度)，整体 O(n + 结果长度)。

简单说就是，时间上你只需要两趟线性扫描加若干次子串比较，空间上多开了一个和原字符串一样长的数组。这种开销在 LeetCode 场景下完全无压力，代码的简单性比微小的性能差异重要得多。

2.4 标记法的两个隐藏细节

第一个细节：为什么判断处要写match[idx] == -1？因为可能存在两个操作从同一个位置开始，两个都能匹配，但我们只能替换一次。按题目给定的操作顺序，保留最先匹配的那个，后面的一律不处理。如果去掉这个判断，后面的操作会把前面的标记覆盖掉，语义就变了。虽然题目大概率不会设计这种极端用例，但在严格讨论题解时，这个保护逻辑是必要的。

第二个细节：为什么索引越界要提前检查？C++ 的 compare 要求 pos 必须在字符串长度范围内，否则直接抛异常。所以idx + sources[i].size() <= n必须先判断。Python 的 startswith 越界时其实不会抛异常，但在 C++ 里这是硬性要求，想要两种语言行为一致，把检查统一写上最稳。

3. 解法二：排序处理法（换一种思路，面试加分）

3.1 排序前先给操作编号

标记法胜在直观，但有的面试官会问：能不能不额外开 match 数组？这时候可以聊排序处理法。核心思想是给操作按 indices 排个序，然后从左到右一边扫描原始字符串，一边处理操作。

排序有个前提：你不能丢掉操作原本的编号，因为 targets 和 sources 都依赖于 i。所以先搞一个 order 数组，里面存 0..k-1，然后按 indices[id] 的大小排序：

vector<int> order(k); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int a, int b) { return indices[a] < indices[b]; });

如果你直接对 indices 排序，排完序后下标和 sources、targets 的对应关系就丢了。这就像你手里有三张名单，你只把第一张按年龄排序，另外两张不跟着动，那三张名单就废了。很多第一次写排序法的人都会在这里翻车。

3.2 从前往后拼接的实现

排完序之后，维护一个指针 cur，表示当前已经扫描到原始 s 的哪个位置。对每个操作 id，它的起点是 idx = indices[id]。处理逻辑是：先把 s 中 [cur, idx) 这一段原样拷贝进答案，因为这些位置没有任何操作覆盖；然后判断 idx 位置是否匹配，匹配就拼 target，并把 cur 跳到 idx + len(src)；不匹配就什么都不拼，cur 保持 idx。所有操作处理完，再把 [cur, 结尾) 的剩余字符拷贝进去。

这里有个容易写崩的细节：如果前面的某个替换源串比较长，把后面的操作起点覆盖了，cur 会大于 idx。这时直接跳过这个操作，不要再做任何拼接。如果不做保护，s.substr(cur, idx - cur)里的 idx - cur 会变成负数，size_t 一转型就是天文数字。

安全的实现我用 while 逐字符拷贝，而不是 substr：

class Solution { public: string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) { int k = indices.size(); vector<int> order(k); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int a, int b) { return indices[a] < indices[b]; }); string ans; int cur = 0; for (int id : order) { int idx = indices[id]; if (idx < cur) continue; // 这个操作已被前面的替换覆盖 while (cur < idx) ans += s[cur++]; // 拷贝未被操作覆盖的原字符 int len = sources[id].size(); if (idx + len <= s.size() && s.compare(idx, len, sources[id]) == 0) { ans += targets[id]; cur += len; } } while (cur < (int)s.size()) ans += s[cur++]; return ans; } };

这段代码在逻辑上比标记法绕一些，但好处是不需要额外开 match 数组。需要注意的是，用 while 逐字符拼接相比 substr 会多几次单字符 append，不过对于 n 最大 1000 的量级完全无所谓，换来的安全性是值得的。如果你真的对性能有执念，可以先ans.append(s, cur, idx - cur)，但前提是必须先保证 cur <= idx，所以跳过的保护判断必不可少。

3.3 从后往前替换的思路（不推荐直接改原串）

排序之后还有一种思路是倒着处理。既然后面的替换不会影响前面字符的索引，有人会想从后往前直接修改原字符串。如果题目保证所有操作互不重叠，这种写法是可行的：从最靠后的操作开始，命中就替换，然后继续往前。

但一旦出现重叠操作，倒序替换的判定会互相污染。比如 s = "aaaa"，两个操作分别是 idx=0 的 "aa" 换成 "X" 和 idx=1 的 "aa" 换成 "Y"。倒序执行时，idx=1 的 "aa" 先被替换，字符串变成 "aYaa"，然后 idx=0 再去判断 "aa" 开头，发现已经不匹配了，于是第一个操作失效。这和“同时替换”的正确语义不一致，正确结果应该是 "Xaa"。所以从后往前直接改原串只适用于严格不重叠的场景，作为通用解法风险很高。

如果你真的想用倒序，正确做法是从后往前构造新字符串，而不是在原串上 insert/erase。但那本质上又回到了“从右往左扫描标记”，代码复杂度和标记法差不多，收益不大。所以综合来看，从后往前这个思路面试时可以提一嘴，展示你知道有这回事，但实现上不推荐。

3.4 两种解法的对比

标记法和排序法本质是一个思路的两种投影。标记法是“空间换简单”，额外开一个数组，把“判断”和“执行”彻底分离，代码不容易出错。排序法是“时间换空间”，不额外开 match 数组，但要对操作排序，还要额外处理覆盖问题，代码复杂度更高。

如果让我选，LeetCode 场景里无脑用标记法。K 最多 1000，O(k*L) 的预标记完全够用。但排序法在系统设计面试里更常出现，因为那种场景下输入往往来自多个数据源，需要先按位置归并，排序是标准动作。两种都值得掌握，至少知道另一个解法存在，面试被追问时有东西可聊。

4. 匹配判断与边界条件：最容易翻车的地方

4.1 判断“以sources[i]开头”的正确姿势

判断一个位置是不是以某个子串开头，最直接的想法是截取出来比一比：

if (s.substr(idx, len) == sources[i]) { ... }

这能跑通，但不推荐。substr 每次都会构造一个临时字符串，如果 len 很长或操作很多，会白白浪费时间和内存。C++ 推荐直接用 compare：

s.compare(idx, len, sources[i]) == 0

意思是：字符串 s 从 idx 开始、长度为 len 的子串，与 sources[i] 比较是否相等。Python 里对应的是：

s.startswith(src, idx)

这个方法返回布尔值，简单直接。养成用非截断方式的习惯，遇到大数据量时差距会很明显。尤其是如果以后把这段逻辑搬到一个高频调用的服务里，每多一次无意义的字符串构造，都可能成为性能瓶颈。

4.2 索引越界与空串

操作给出的 indices[i] 保证在 [0, n) 内，但 indices[i] + sources[i].size() 可能超过 n。也就是说，源串要求的匹配区间超出了 s 的末尾，这种操作肯定不匹配。C++ 里不做越界检查直接 compare，会抛 out_of_range，所以必须先判断：

idx + sources[i].size() <= n

Python 的 startswith 即使 pos 后面不够长，也会安全返回 False，所以很多人会忽略这个检查。但为了让代码语义清晰，建议两种语言都写上。另外源串长度题目保证至少是 1，所以不用处理空 sources 这种特殊情况。如果哪天你把代码改成通用工具，空 sources 的判断规则也要提前想清楚：空串在任何位置都匹配，替换会产生什么结果，最好单独处理。

4.3 重叠与索引相同的冲突处理

重叠是这道题最有意思的地方。假设 s = "aaaa"，两个操作分别是 idx=0, src="aa" 和 idx=1, src="aa"，两个都能匹配。按“同时替换”的语义，我们应该怎么处理？

答案是：从左到右构造结果时，第一个操作先命中，idx=0 的 "aa" 被替换成 "X"，然后游标直接跳到 2。第二个操作虽然基于原始 s 是匹配的，但它所在的 [1, 3) 区间和前面替换区间重叠，最终会被吞掉，不会生效。所以结果是 "X" + 原始 s[2..4]，即 "Xaa"。你可以理解为：所有匹配先判定，但输出时按位置从左到右，一旦某个位置被替换占用，后面起点落在该区间内的操作自动失效。这点不看透，遇到重叠数据会完全蒙圈。

同样的道理也适用于索引相同的情况。如果两个操作的 indices 相同，但只有其中一个匹配，那么匹配的那个生效。如果两个都匹配，按操作数组中的先后顺序，先出现的生效。标记法里用match[idx] == -1来控制，就是为了保证这个“先到先得”的行为。

4.4 边界用例整理

平时我刷这种字符串题，习惯把边界用例收集成一个表格，方便随手自测，这里也整理一份：

这个表基本覆盖了这道题的坑。建议你写完代码后手动跑一遍这六组，全过说明大概率没问题，再去提交。尤其是“替换为空串”那个用例，能顺便检验你的指针移动逻辑：替换为空时，游标应该跳 source 的长度还是跳 0？跳 0 会死循环，跳 source 长度才是对的。

5. 真实踩坑记录与调试技巧

5.1 三种典型的错误写法

第一种：顺序原地替换。循环里每次都s = s[:idx] + target + s[idx + len(src):]，然后继续遍历。这种写法在操作互不重叠时能过，一旦源串长度不同，前后的下标全乱，直接 WA。

第二种：排序后忘记记录原始编号。只对 indices 排序，然后直接拿排序后的索引去取 sources/targets，取出来的数据和 indices 对不上。必须先把操作编号装进 order 数组再排序。

第三种：省略越界检查。C++ 里直接s.compare(idx, len, src)，当 idx + len > s.size() 时抛异常，本地调试可能通过部分用例，提交时直接 Runtime Error。

这三种错误我都实际犯过，尤其是第一种，几乎每个写这道题的人都至少交过一次。不是算法不懂，而是思维惯性太强，总觉得“替换”就是立刻改字符串。把“判断”和“执行”彻底分开想，这类错误就消失了。

5.2 怎么用暴力法做对拍

面对这种“所有判断基于原串，再一次性输出”的题，