字符串替换这个考点在牛客网的笔试和面试手撕题里出现的频率其实比很多人想象的高。题目本身看着简单——给定一个原始字符串把其中某个子串全部替换成另一个子串要求用C实现——但真正上手写深浅不一的坑却不少。我自己最初写这题时也改过好几版代码不是死循环就是漏替换后来把思路彻底理清了才稳定跑通。这篇文章就围绕牛客网这道字符串替换题从题目理解、算法设计、C代码实现到边界条件测试完整讲一遍适合正在刷题准备面试的C选手也适合想巩固字符串基本功的同学参考。1. 题意拆解这题考的到底是什么1.1 题目输入输出形式牛客网上的典型输入形式是输入三行第一行是原始字符串s第二行是待替换子串a第三行是替换目标子串b要求输出替换后的完整字符串。比如hello world world everyone期望输出hello everyone这里要求的是全部替换不是只替换第一次出现。如果s中有多处a每一处都要替换成b。这是题目最容易踩的语义坑之一后面我会单独展开。1.2 容易理解偏的三个地方我见过不少同学包括我自己一开始在这几个点上理解偏了第一替换是子串替换不是字符替换。有人以为是把字符串中某个字符全部换掉实际上替换目标可以是一段连续的字符序列长度也不必和原串一样。这个区别直接影响匹配逻辑的写法。第二要处理的是全部出现位置而不是只处理第一个。如果只找到第一次出现的位置就停手输出就错了。牛客这类题目几乎默认是全替换除非题目明确说“只替换首次出现”。第三替换的元素是输入字符串本身不是我们手动挑出来的一小段。有些同学图省事只对从find返回的位置做局部处理忽略了替换后剩余部分还要继续参与后续匹配导致漏掉后面的相同子串。我在实际刷题时发现题意没有理解偏的话后面代码写起来会顺很多。每次写字符串相关题目我都会先在心里把题目重新翻译一遍输入是什么、输出是什么、边界条件是什么。题解读多了会发现这类题真正想考察的并不是“会不会调用某个现成函数”而是匹配逻辑是否严谨、边界意识是否到位。2. 核心思路为什么我选择逐字符扫描拼接新串2.1 方案对比STL replace、find循环、扫描拼接拿到题目很多人的第一反应是直接用C标准库的string::replace。replace本身确实能完成替换但问题在于它一次只能处理一处位置你需要自己循环查找和更新位置。我也见过有人用find加erase加insert来写代码量很少while ((pos s.find(a)) ! std::string::npos) { s.erase(pos, a.size()); s.insert(pos, b); }这段代码在简单场景下能跑通但存在一些隐患。我做了个对比方案思路优点缺点finderaseinsert每次找到子串后原地删除再插入代码短直观多次内存搬移替换后位置索引易出错极端输入可能死循环replace 前缀索引用偏移量定位循环调用replace标准库封装好每次替换都会触发字符串内部重新分配性能一般逻辑绕逐字符扫描拼接新串遍历原串匹配到子串则追加替换串并跳过否则追加当前字符只扫一遍逻辑清晰不需要反复修改原串需要额外空间构造结果最终我选择的是逐字符扫描加拼接新串。这个方案的优势不在于代码最短而在于思路最不容易出错尤其适合手撕代码的场景。面试时你不需要和面试官解释复杂的索引跳跃逻辑只要说清楚“扫描原串匹配到就跳过并追加替换串”对方就能立刻理解。2.2 逐字符匹配背后的两个关键决策第一个决策是匹配时使用std::string::compare还是手写逐字符比较。compare(pos, count, str)可以比较从某个位置开始的子串是否等于目标子串用法简洁。但有两点需要注意pos不能越界否则会抛出std::out_of_range异常如果从pos开始的字符数不足目标子串长度比较结果天然不相等这正好符合我们的预期。我在代码里加了i m n的前置判断既防止越界也让逻辑更加清晰可读。第二个决策是匹配成功之后索引跳过的长度是多少。这里有个容易混淆的点。假设s是aaaaa是aab是b。如果每次匹配成功就把下标往前移动a.size()那么替换结果是bb如果匹配成功只让下标移动一个字符结果就完全不同甚至会得到一种“重叠替换”的效果。牛客这类题目的语义是不重叠替换也就是说替换完一个子串之后把它看作已经处理完的部分继续向后扫描所以下标要一次性跳过待替换子串的长度。这个决策如果不提前想清楚写出的代码会时对时错换几个测试用例就露馅。3. C实现细节这版代码为什么这么写3.1 完整代码与关键点说明下面是我最终通过测试的完整实现#include iostream #include string std::string replaceSubstring(const std::string s, const std::string a, const std::string b) { // 待替换子串为空时直接返回原串避免后续逻辑死循环 if (a.empty()) { return s; } std::string result; // 预分配空间减少后续扩容带来的拷贝开销 result.reserve(s.size()); size_t i 0; const size_t n s.size(); const size_t m a.size(); while (i n) { // 如果剩余长度足够并且从 i 开始的子串等于 a则进行替换 if (i m n s.compare(i, m, a) 0) { result.append(b); i m; // 跳过已匹配的子串避免重叠替换 } else { result.push_back(s[i]); i; // 普通字符逐个拷贝 } } return result; } int main() { std::string s, a, b; // 三行输入原始串、待替换串、替换串 std::getline(std::cin, s); std::getline(std::cin, a); std::getline(std::cin, b); std::cout replaceSubstring(s, a, b) std::endl; return 0; }有几个细节我想特别说明。第一为什么用std::getline而不是std::cin s。如果待替换串或原始串中包含空格cin会截断输入导致读入不完整。用getline可以完整读取一整行。牛客网有些题目字符串中不会出现空格但保险起见我还是习惯用getline。第二为什么先特判a.empty()。如果不特判当a为空串时s.compare(i, 0, )会返回相等然后i 0循环永远不前进直接死循环。这种坑只会在特定输入下触发一旦笔试环境里出现调试起来会浪费大量时间。第三为什么用result.reserve(s.size())。替换后的字符串可能比原串长也可能比原串短。预先分配原串长度的空间可以避免在append过程中反复扩容。std::string扩容时通常伴随着元素拷贝虽然现代std::string用了移动语义但减少扩容次数仍然能明显提升大输入下的效率。3.2 测试用例从基础场景到刁钻场景我把自己在本地跑过的测试用例整理在下面供参考输入期望输出测试意图sabcabc, aabc, bxxx多位置替换且替换后缩短sabcabc, abc, bBCaBCaBC替换串不影响不相邻部分saaaa, aaa, bbbb不重叠替换的语义确认shello, all, bheo替换为空串等价于删除sa, aa, bbbbbbb替换后显著变长s, aabc, bx空原串sabc, a, bxabc空待替换串防止死循环saXbXc, aX, bYZaYZbYZc普通多字符替换第4个用例尤其值得注意它说明了一个事实这道题的“替换子串”完全可以为空串来实现删除效果。这个结论在面试中经常被追问可以作为扩展点聊。4. 边界情况与踩坑实录那些让我改了三版的问题4.1 空串与极端输入循环条件必须防呆字符串处理题的边界条件往往决定了代码的鲁棒性。我最初写第一版时完全没有处理待替换子串为空的情况结果本地测试一传入空串程序直接卡死。原因是find函数对空字符串有特殊行为s.find()返回0。如果用while ((pos s.find(a)) ! npos)的写法find永远能找到位置0erase删掉0个字符insert又在位置0插入位置始终是0循环永远结束不了。所以处理空串的第一原则就是显式特判尽早返回。不管采用哪种方案这道题都应该在进入主逻辑之前把a.empty()排除掉。另一个极端是原串为空。原串为空时循环体根本不会进入直接返回空串这个天然是安全的。不过我还是习惯把它写进测试用例里跑一遍确认无误再说防的就是以后代码逻辑改了之后引入回归问题。4.2 重叠子串与索引移动不重叠替换到底怎么实现我第二版代码踩的坑是索引移动。最初我用的是for循环i写在循环尾部for (size_t i 0; i s.size(); i) { if (匹配成功) { result.append(b); i a.size() - 1; // 减一是为了抵消循环末尾的 i } }这段代码看起来能工作但很容易看晕为什么这里要减1如果a.size()恰好等于0怎么办减1会不会下溢成SIZE_MAX类似这种写法在代码审查和面试陈述里都不够直观。我后来改成while循环把索引移动完全掌握在自己手里。匹配成功时i m不成功时i每一步都清清楚楚。重叠子串的问题也在这里一并解决。所谓“不重叠替换”就是在匹配成功时把整个已经匹配的子串从候选区里摘出去。比如原串是aaaa待替换串是aa替换串是b扫描过程如下从位置0开始发现aa匹配追加b索引跳到2。从位置2开始发现aa匹配追加b索引跳到4。循环结束结果是bb。如果匹配成功时索引只移动一位结果就会变成baa这通常不是题目期望的语义。刷题之前先明确“重叠还是不重叠”能省去后面的大量猜测。4.3 输入读取与编码一个容易被忽视的细节牛客网这类在线评测平台输入通常是多行文本。如果第一行字符串里含空格并且题目没有提前说明直接用std::cin s会把空格后面的内容当成下一行输入导致解析错乱。我一个朋友就因为在输入读取上偷懒本地测得好好的平台上一跑就错。我自己的习惯是只要题目没有明确说“字符串不含空格”一律用std::getline读整行。即使题目确实不含空格getline也不会带来兼容性问题只是少了一点“简洁感”但换来的是更稳的行为。另一个输入相关的坑是和换行符有关的。如果前面用std::cin读过一个整数再接着用getline读字符串缓冲区里的换行符会被getline直接吃掉导致读到的字符串是空串。这个经典问题在笔试题里非常常见。正确做法是读完整数后用getline把残留换行消费掉或者统一都用getline。4.4 越界隐患compare的位置参数不是百无禁忌std::string::compare的pos参数如果超过字符串长度会抛出std::out_of_range。虽然这个异常在牛客网上很少被触发但一旦触发程序可能直接崩溃评测结果为运行时错误。我在代码里写的条件是i m n s.compare(i, m, a) 0这个前置条件同时保证了两件事一是剩余长度足够容纳一次完整比较二是i本身一定在合法范围内因为i n是外层循环的不变量。可能有人会问如果i m n直接调用compare是不是也能得到“不匹配”的结果确实compare在这种情况下会比较从i到末尾的剩余子串与a的前缀结果不相等。这种做法在功能上没错但读代码的人需要多想一想才知道“为什么这样写也安全”。加上显式的前置判断代码意图更直白也方便以后扩展逻辑。我最终选择的是更直白的那一版。5. 复杂度分析与面试扩展考法5.1 时间复杂度与空间复杂度这道题的时间复杂度是O(n*m)其中n是原串长度m是待替换子串长度。最坏情况下从每个位置开始都要做一次长度为m的比较比如原串aaaaaaaa、待替换串aaaaab的时候。空间复杂度是O(n)因为结果字符串的长度与原串和替换串有关理论上最坏情况下结果串长度可能达到n/m * b.size()但为了简化分析多数面试场景下说O(n)就足够了。如果追求更优的匹配性能可以考虑KMP算法把匹配过程优化到O(nm)。但在这道题里原串和待替换串的长度通常有限O(n*m)在实际笔试中完全够用。面试时如果能主动说出“这是暴力匹配最坏情况是O(n*m)需要优化时可以用KMP”会显得思路比较完整。5.2 从这道题延伸出的高频变体字符串替换这道题在面试里经常会演化出几个变体。第一个变体是统计子串出现次数。只需要把result.append(b)换成计数器累加i m的逻辑完全复用。刷过这题之后统计子串次数就变成了一道“改一行”的题。第二个变体是删除指定子串。把替换串b设为空串代码无需任何改动就能实现删除所有指定子串的效果。这比用erase循环逐个删除更高效因为同样只需要扫描一遍。第三个变体是替换后继续对替换结果进行匹配比如LeetCode风格的“多次替换”题。这种变体就不能用单遍扫描解决了通常需要用递归或循环反复处理直到字符串不再变化。它考察的就是对循环终止条件和字符串变化的敏感度。这几种变体在牛客网评论区、C面试八股里都很常见。字符串题从来不单纯考API调用更多是考处理逻辑和边界意识。我在准备面试时发现能把一道简单题的各种变体和边界条件讲清楚比刷十道同类题更有帮助。我的经验是每做完一道字符串题都顺手把自己的解法改成几个变体跑一遍能极大提高手撕代码的稳定度。这道题我从第一版到最终版改了三次每一次都是被边界测试用例教育出来的。如果你现在正在刷类似的题建议把我上面列的那张测试用例表复制到本地跑一遍自己的实现再对照看哪些用例没过查漏补缺字符串处理的底子就是这么一点点磨出来的。