LeetCode 833这道题我印象挺深。名字叫《字符串中的查找与替换》听起来像一个基础题实际上坑全埋在“查找与替换”这几个字里。很多人第一次写完会得到错误答案不是不会匹配而是把“同时替换”理解成了“按顺序逐个替换”。这篇文章咱们就从头把这个题捋一遍从题面语义、两种主流写法到索引越界、重叠冲突这些容易翻车的细节最后再聊几个工程里的类似场景。无论你是刚开始刷题准备面试还是已经刷了几百题想查漏补缺这一篇应该都有点用。1. 题目到底在说什么别被“替换”两个字带偏1.1 原题语义与示例把题目翻译成大白话给你一个原始字符串 s三个长度相同的数组 indices、sources、targets。对于第 i 个操作你去看 s 中从 indices[i] 开始的位置是不是正好以 sources[i] 开头。是的话就把这一段替换成 targets[i]不是的话这个操作直接忽略。所有操作都是基于原始的 s 来判定最终一次性返回所有替换之后的结果。“基于原始 s 判定”这一点是理解整道题的钥匙。举个例子你就明白了。s abcdindices [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[idxlen(src):]大部分用例会挂。为什么因为你的 s 已经变了位置会错乱。比如还是 abcd假设只有一个操作 indices[2]sources[cd]你先替换成 abY这没问题但如果后面还有一个 indices[1] 的操作你原本希望它在原始 s 的 b 上判断现在 s 变成 abYb 的位置没变还好一旦源串长度不一样比如把 ab 换成 Xs 变成 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/PythonC 代码class Solution { public: string findReplaceString(string s, vectorint indices, vectorstring sources, vectorstring targets) { int n s.size(), k indices.size(); vectorint 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] 的大小排序vectorint 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 逐字符拷贝而不是 substrclass Solution { public: string findReplaceString(string s, vectorint indices, vectorstring sources, vectorstring targets) { int k indices.size(); vectorint 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两个操作分别是 idx0 的 aa 换成 X 和 idx1 的 aa 换成 Y。倒序执行时idx1 的 aa 先被替换字符串变成 aYaa然后 idx0 再去判断 aa 开头发现已经不匹配了于是第一个操作失效。这和“同时替换”的正确语义不一致正确结果应该是 Xaa。所以从后往前直接改原串只适用于严格不重叠的场景作为通用解法风险很高。如果你真的想用倒序正确做法是从后往前构造新字符串而不是在原串上 insert/erase。但那本质上又回到了“从右往左扫描标记”代码复杂度和标记法差不多收益不大。所以综合来看从后往前这个思路面试时可以提一嘴展示你知道有这回事但实现上不推荐。3.4 两种解法的对比标记法和排序法本质是一个思路的两种投影。标记法是“空间换简单”额外开一个数组把“判断”和“执行”彻底分离代码不容易出错。排序法是“时间换空间”不额外开 match 数组但要对操作排序还要额外处理覆盖问题代码复杂度更高。如果让我选LeetCode 场景里无脑用标记法。K 最多 1000O(k*L) 的预标记完全够用。但排序法在系统设计面试里更常出现因为那种场景下输入往往来自多个数据源需要先按位置归并排序是标准动作。两种都值得掌握至少知道另一个解法存在面试被追问时有东西可聊。4. 匹配判断与边界条件最容易翻车的地方4.1 判断“以sources[i]开头”的正确姿势判断一个位置是不是以某个子串开头最直接的想法是截取出来比一比if (s.substr(idx, len) sources[i]) { ... }这能跑通但不推荐。substr 每次都会构造一个临时字符串如果 len 很长或操作很多会白白浪费时间和内存。C 推荐直接用 compares.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() nPython 的 startswith 即使 pos 后面不够长也会安全返回 False所以很多人会忽略这个检查。但为了让代码语义清晰建议两种语言都写上。另外源串长度题目保证至少是 1所以不用处理空 sources 这种特殊情况。如果哪天你把代码改成通用工具空 sources 的判断规则也要提前想清楚空串在任何位置都匹配替换会产生什么结果最好单独处理。4.3 重叠与索引相同的冲突处理重叠是这道题最有意思的地方。假设 s aaaa两个操作分别是 idx0, srcaa 和 idx1, srcaa两个都能匹配。按“同时替换”的语义我们应该怎么处理答案是从左到右构造结果时第一个操作先命中idx0 的 aa 被替换成 X然后游标直接跳到 2。第二个操作虽然基于原始 s 是匹配的但它所在的 [1, 3) 区间和前面替换区间重叠最终会被吞掉不会生效。所以结果是 X 原始 s[2..4]即 Xaa。你可以理解为所有匹配先判定但输出时按位置从左到右一旦某个位置被替换占用后面起点落在该区间内的操作自动失效。这点不看透遇到重叠数据会完全蒙圈。同样的道理也适用于索引相同的情况。如果两个操作的 indices 相同但只有其中一个匹配那么匹配的那个生效。如果两个都匹配按操作数组中的先后顺序先出现的生效。标记法里用match[idx] -1来控制就是为了保证这个“先到先得”的行为。4.4 边界用例整理平时我刷这种字符串题习惯把边界用例收集成一个表格方便随手自测这里也整理一份输入 s操作期望结果说明abcdindices[0,2], sources[ab,cd], targets[X,Y]XY基础替换abcdindices[0,1], sources[ab,ec], targets[X,Y]Xbcd第二个不匹配原样保留abcindices[0,0], sources[x,ab], targets[1,2]2c同起点先不匹配后匹配aaaaindices[0,1], sources[aa,aa], targets[X,Y]Xaa重叠区间靠左优先abcdeindices[2], sources[cde], targets[Z]abZ替换到字符串末尾abcindices[0], sources[abc], targets[]替换为空串这个表基本覆盖了这道题的坑。建议你写完代码后手动跑一遍这六组全过说明大概率没问题再去提交。尤其是“替换为空串”那个用例能顺便检验你的指针移动逻辑替换为空时游标应该跳 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 怎么用暴力法做对拍面对这种“所有判断基于原串再一次性输出”的题