字符串题在力扣里出现的频率只要刷过两周的人应该都有体会说它是半壁江山不算夸张哪怕保守点把数组、动态规划也算进去字符串依然是绕不过去的那一道坎。很多人一看到字符串就觉得是“背函数”什么split、reverse、toLowerCase调完就AC真遇到卡人的题就懵。我之前也这么想过直到刷了大几十道字符串题之后才意识到字符串题真正考的东西其实很统一就三样双指针、哈希表、动态规划再加一个KMP偶尔出来吓唬人。这篇文章我就围绕这几个方向结合我在力扣上刷过的经典题目把字符串题从套路到实战完整梳理一遍适合刚开始刷题的人打基础也适合刷了一定数量但总是差临门一脚的同学整理思路。1. 先把话说清楚字符串题到底在考什么1.1 字符串的本质是“带性格的字符数组”字符串在底层就是字符数组这是理解所有字符串题的第一性原则。在C/C里是char[]或以\0结尾的字符序列在Java里是char[]加不可变封装在Python里是str不可变对象。但不管语言怎么封装抽象层面你要时刻把它当成一个有序的、可索引的字符序列来处理。这个“有序可索引”意味着什么意味着你在数组题里用过的一切技巧双指针、二分、前缀和、差分、单调栈理论上都能搬到字符串上来。比如力扣344题“反转字符串”它本质上就是数组反转双指针从两端往中间走交换字符一行思路都不用改。再比如力扣28题“找出字符串中第一个匹配项的下标”本质就是在一个数组里找子数组的匹配位置只是把数字换成了字符。但字符串也有自己的“性格”主要体现在三点。第一字符的取值空间有限。数字可以是任意大小但字符一般就是ASCII的128个或扩展的256个或者Unicode的几万个。有限取值空间意味着你经常会用一个长度为128或256的数组来当哈希表用这比用HashMap快得多。第二字符串有“字典序”这种天然的比较规则所以排序题在字符串里特别多比如力扣179题“最大数”表面是排序实际是自定义比较器的事。第三字符串拼接和切分的成本往往不是O(1)的尤其在Java和Python这类不可变字符串的语言里频繁拼接会产生大量中间对象这也是很多字符串题优化空间的来源。1.2 字符串题的五种常见“包装”字符串题之所以看着杂是因为同样一个底层考点它可以打扮成各种样子来考你。我刷了这么多道整理了五种最常见的“包装”。第一种是回文类。回文串就是正着读倒着读一样的字符串比如aba、abba。这类题的核心考点是双指针或中心扩展经典题有力扣125“验证回文串”、力扣5“最长回文子串”、力扣647“回文子串”数量。第二种是子串/子序列类。子串是连续的子序列可以跳着取。连续子串的问题十有八九用滑动窗口不连续的子序列问题基本都靠动态规划。经典题有力扣3“无重复字符的最长子串”、力扣76“最小覆盖子串”、力扣1143“最长公共子序列”。第三种是匹配/查找类。在一个长串里找一个模式串是否出现或者找第一个出现位置。这类最简单的是暴力匹配进阶是KMP、Boyer-Moore、Sunday这些字符串匹配算法。力扣28题是标准入口。第四种是变形/转换类。比如大小写转换、字符串转数字、压缩解压、反转单词等。这类题往往看起来简单但坑很多。力扣8题“字符串转换整数(atoi)”就是典型的看似简单却能把你绕晕的题各种空格、正负号、越界、非法字符的边界条件能把人磨疯。第五种是组合构造类。比如电话号码的字母组合、括号生成、分割回文串等基本是回溯/DFS的舞台字符串只是作为结果展示的载体。一旦你能把一道新题拆解成“包装 核心考点”刷题效率会高很多遇到没见过的题也不会慌。下面我就按核心考点来展开这些才是真正要背下来、练熟的东西。2. 字符串题的三板斧双指针、滑动窗口、哈希表2.1 双指针从两边逼近还是从同向出发双指针在字符串里有两个流派相向指针和同向指针。相向指针通常用于回文串、反转类题目一个指针在头一个指针在尾按条件向中间移动。同向指针就是两个指针都从左边出发一个快一个慢实际上这就是滑动窗口的基础形态。力扣344“反转字符串”是相向指针最简单也最典型的题void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } }力扣125“验证回文串”同样是相向指针但多了一个细节只考虑字母和数字且忽略大小写。于是你需要在指针移动的时候跳过非字母数字字符再统一转成小写来比较。很多人在这种“跳过比较”的组合上犯错跳过之后忘记检查left right导致越界。这是相向指针最容易踩的坑。再进阶一点是力扣345“反转字符串中的元音字母”。这题的思路和反转字符串完全一样只不过交换的条件变成了“当前指针指向的是元音字母”。注意题目里元音字母是包含大小写的aeiouAEIOU少写一个就出Bug。同向双指针我放在滑动窗口里一起讲因为它们其实是同一个东西。但这里要竖一个观点双指针不只是用来降低复杂度的更重要的是它能帮你把“涉及区间”的题目想清楚边界。每次移动left或right的时候你要在心里明确当前区间[left, right]代表什么代表什么字符集合这样的区间是否合法。想不清楚边界刷十道题错十道。2.2 滑动窗口最长子串的万能钥匙滑动窗口解决的是一类经典问题连续子串/子数组求满足某条件的最长或最短长度。它之所以高效是因为每个字符最多被left和right各访问一次时间复杂度O(n)。拿力扣3“无重复字符的最长子串”来说这是滑动窗口的入门题但它是后面一大堆难题的母题。核心思路right指针不断向右扩展把新字符加入窗口如果发现窗口中已经有重复字符就移动left指针缩小窗口直到没有重复为止。怎么判断有没有重复哈希表或长度为128的数组记录字符最后一次出现的位置。int lengthOfLongestSubstring(string s) { vectorint last(128, -1); int left 0, ans 0; for (int right 0; right s.size(); right) { if (last[s[right]] left) { left last[s[right]] 1; } last[s[right]] right; ans max(ans, right - left 1); } return ans; }这里有个非常关键的点if (last[s[right]] left)。为什么不是if (last[s[right]] ! -1)因为last数组里存的是字符上一次出现的位置但这个位置可能已经在窗口之外了。如果它出现在left之前说明虽然这个字符之前出现过但已经不属于当前窗口不影响我们。只有上一次出现位置在窗口内即 left才真正造成重复。这个细节我当初看题解时想了很久画了好几遍窗口才彻底明白。力扣76“最小覆盖子串”是滑动窗口的进阶题也是我当年刷到“怀疑人生”的题。它要求找出s中包含t所有字符的最短子串。做法是先统计t中每个字符的需求量然后right扩展找可行解再移动left找最优解同时维护一个valid变量表示当前窗口中有多少个字符已经满足了需求。这个过程里你要时刻更新valid而且在收缩窗口的时候注意检查收缩后的窗口是否仍然满足条件不满足就继续扩展right。这个题可以说是检验滑动窗口是否真正理解的分水岭能把76题自己写出来滑动窗口基本就过关了。2.3 哈希表异位词和频次统计的利器哈希表在字符串里的角色是“频次统计”和“快速查找”。力扣242“有效的字母异位词”是最基本的统计两个字符串中各字符出现的次数完全相等就是异位词。由于只有小写字母可以直接用长度为26的数组根本不需要哈希表。力扣49“字母异位词分组”稍微升级一点给定一组字符串把异位词分到同一组。核心在于“如何定义异位词的键”。两个常见做法一是把每个字符串排序后作为键因为异位词排序后结果是相同的二是统计每个字符串中26个字母的出现次数序列化成一个数组或字符串作为键。用排序法代码最简单vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring mp; for (string s : strs) { string key s; sort(key.begin(), key.end()); mp[key].push_back(s); } vectorvectorstring ans; for (auto p : mp) ans.push_back(p.second); return ans; }这里我踩过一个坑用排序后的字符串当key没问题但如果你把key定义成“字符出现次数拼接的字符串”要小心数字的歧义。比如12到底是“1个a2个b”还是“12个a”所以正确的做法是用带分隔符的序列化或者直接用一个引用计数为0的数组加自定义哈希函数。这类序列化细节在面试里很爱被追问平时刷题就要注意。哈希表还有一个高频场景是“找两个字符串的公共字符”“字符串中第一个唯一字符”力扣387之类。核心无非是先扫一遍记录频次再扫一遍按条件找答案。这类题不难但有一个共通的优化点能用数组就不要用unordered_map尤其在字符集有限ASCII的情况下数组的访问是O(1)且常数极小而unordered_map每次操作都有哈希计算和潜在的冲突处理成本。力扣上很多字符串题的题解区都在强调这一点。3. 高频经典题实战拆解从暴力到最优3.1 “最长回文子串”的三种做法对比力扣5“最长回文子串”是字符串题里的常青树解法多到可以写一篇论文。先把三种主流做法对比清楚你才能理解为什么推荐中心扩展。第一种是暴力枚举所有子串逐一判断是否回文。时间复杂度O(n^3)基本只适合用来验证小数据。第二种是动态规划定义dp[i][j]表示s[i..j]是否为回文串转移方程是dp[i][j] (s[i] s[j]) dp[i1][j-1]注意要从短的子串向长的子串递推时间复杂度O(n^2)空间也是O(n^2)。第三种是中心扩展法遍历每个中心包含单字符中心和对双字符中心两种情况向左右扩展统计每次扩展的最大长度时间复杂度O(n^2)但空间O(1)。我第一次写这题用的是动态规划后来发现中心扩展代码更简洁直观string longestPalindrome(string s) { int n s.size(); auto expand [](int l, int r) { while (l 0 r n s[l] s[r]) { l--; r; } return r - l - 1; }; int start 0, maxLen 0; for (int i 0; i n; i) { int len1 expand(i, i); int len2 expand(i, i 1); int len max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } len max(len1, len2); } return s.substr(start, maxLen); }中心扩展的启动位置计算是个容易写错的地方。如果回文串长度为奇数中心是s[i]长度为偶数中心在s[i]和s[i1]之间。算start时用的是i - (len - 1) / 2因为len是从中心向两边扩展的总长度。这个公式我建议直接记住现场推容易在边界上翻车。还有一个更高阶的算法叫Manacher马拉车复杂度O(n)。它通过在字符之间插入特殊符号如#把奇数长度和偶数长度的回文串统一成奇数长度处理同时利用已计算的回文半径数组加速。说实话我在面试里从来没有被要求手写Manacher但理解它的思想对加深“以中心扩展为原型、利用对称性优化”这件事很有帮助。如果你有时间可以看一遍Manacher并手写一遍对自信心的建立很有帮助。3.2 字符串匹配KMP算法的前因后果力扣28题“找出字符串中第一个匹配项的下标”是最经典的字符串匹配入口。暴力做法是从原串的每个位置开始尝试匹配模式串一旦失配就回退到下一个位置重来。最坏情况时间复杂度O(mn)比如s全是aaaaaaaab模式串是aaaab每匹配到最后一个字符就失配然后从头再来非常浪费。KMP算法的核心思想是在失配的时候不把匹配位置回退到模式串的开头而是利用已经匹配的前后缀信息跳到下一个可能匹配的位置。这个“前后缀信息”就是next数组。next[i]表示模式串的前缀子串p[0..i]中最长相等前后缀的长度。举个例子模式串ababc对子串abab来说最长相等前后缀是ab长度2。构建next数组的代码是KMP最绕的一部分我直接给出常用的写法vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) j; next[i] j; } return next; }这段代码的精髓在于while (j 0 p[i] ! p[j]) j next[j - 1];它其实是在递归失败时利用已有的next信息来缩短回退距离。理解这一行KMP就成功了一半。匹配阶段类似遍历主串s当字符匹配不上时沿着next回退模式串指针j直到重新匹配或j归零。这里要特别提示KMP并不是工程中最常用的字符串匹配算法因为大多数语言的indexOf、find底层用的是优化过的双端匹配算法如Boyer-Moore变体。但KMP在算法面试里是“理解层次”的题它考察的是你有没有真正理解“利用已匹配信息避免重复比较”这个思想。所以就算你只是准备面试也应该至少能默写一遍buildNext和匹配主循环。3.3 从公共子序列到编辑距离二维DP的反复应用字符串的动态规划题十有八九是二维DPdp[i][j]表示“第一个串的前i个字符”和“第二个串的前j个字符”作为子问题的答案。力扣1143“最长公共子序列”就是最基础的二维DP模板。定义dp[i][j]为text1[0..i-1]和text2[0..j-1]的最长公共子序列长度。转移时如果当前两个字符相等dp[i][j] dp[i-1][j-1] 1如果不相等则是max(dp[i-1][j], dp[i][j-1])。这里的“删掉一个字符看剩余”的思考方式是后续所有字符串DP的基础。力扣72“编辑距离”是二维DP的另一座高山。这题的dp[i][j]表示把word1[0..i-1]转换成word2[0..j-1]所需的最小操作数。操作有插入、删除、替换三种。转移方程是如果 word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] 否则: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])这三个选项分别对应删除、插入、替换。我学这题的时候最大困惑在于“为什么删除和插入是对称的”。后来想明白了dp[i-1][j]表示删掉word1当前字符然后继续转换dp[i][j-1]表示在word1当前位置插入一个和word2当前字符一样的字符然后继续转换。一个是删原串一个是补目标串本质上都是“让当前字符对齐”。字符串DP题有一个通用套路先画出二维表手动填几行数你会发现填表逻辑非常直观。很多人在没画表之前看转移方程觉得天书画过一遍之后就觉得“不过如此”。所以你在刷这类题的时候强烈建议在纸上把dp表的前几行自己填一遍比如horse转ros的编辑距离填完你就能理解为什么初始化时第一行和第一列是递增的。4. 容易被问爆的进阶套路排序、分割、大小写转换4.1 字符串排序与比较的隐藏细节字符串排序看起来简单sort(strs.begin(), strs.end())就完事了但实际场景里坑很多。第一个坑是大小写是否敏感。默认的字典序比较中大写字母的ASCII码小于小写字母A是65a是97所以Apple会排在banana前面。如果需求是“忽略大小写排序”你需要自定义比较器把每个字符先tolower再比较。第二个坑是自然排序。对file10和file2字典序排序会得到file10在前因为比较到第5个字符时1比2小。但人类通常期望file2排在file10前面这就是自然排序。力扣179题“最大数”其实也是排序比较器问题把数字转成字符串然后按照“abvsba”的字典序来比较。比如3和30拼接成330和303很明显330更大所以3应该排在30前面。这种自定义比较器的方法是字符串题的一个高频考点我单独强调一下。第三个坑是比较器的严格弱序。C的sort要求比较器必须满足“严格弱序”如果你写的比较函数返回结果不稳定比如a b和b a对同样的输入某一次同时返回true就会导致未定义行为轻则排序乱掉重则直接崩溃。所以自定义比较器时要用return a b b a;这种确定性写法不要在里面搞随机或可变状态。4.2 字符串分割与拼接的边界问题分割字符串在笔试和面试里几乎是必出现的基础操作尤其是在处理命令行参数、CSV、IP地址等场景。力扣没有专门的分割题但它藏在大量题目里比如“翻转字符串里的单词”力扣151。分割最常见的问题是连续分隔符和首尾分隔符。C里如果用istringstream默认会忽略空白字符所以多个空格会被当成一个分隔符处理而如果手动遍历按 分割就要自己跳过连续的空格。Java的split默认会丢弃尾部的空字符串但在某些版本里正则表达式需要小心Python的split()不传参数时会自动处理多个空格。这些语言差异考试和面试时必须心里有数。拼接字符串也有性能坑。在Java和Python中字符串是不可变的每一次拼接都会创建一个新对象。如果在一个循环里拼接大量字符串时间开销会很大。Java里应该用StringBuilderPython里更推荐把片段加入列表最后用.join(list)。这个优化在数据规模小的时候无所谓但力扣的测试数据经常会卡常数养成好习惯能省很多不必要的麻烦。4.3 大小写转换的“坑”不是所有字符都有大小写大小写转换在很多人眼里是无脑操作但力扣709题“转换成小写字母”就设置了陷阱题目要求实现一个函数将字符串转换为小写字母但字符串中可能包含数字、标点、非英文字符。错误做法是直接把每个字符减32这样会把5变成\u0015这种控制符。正确做法是先判断字符是否在A到Z范围内只有大写字母才减32。同理ñ、ß这种非ASCII字符不同语言的toLowerCase处理方式也不一样最好明确题目要求。这条经验延伸到更广的场景任何时候你要对字符做数学加减都要先确认它满足你假设的范围是英文字母、是数字、是ASCII还是UTF-8。我在写力扣8“字符串转换整数(atoi)”的时候就因为没有先判断字符是否为数字就贸然做c - 0结果调试了半天。这种问题不难但极其考验细心程度。5. 刷题路线与排坑手册5.1 力扣字符串题单的正确刷法很多人问字符串题从哪开始刷我的建议是不要按题号顺序刷而是按套路刷。第一阶段把双指针和哈希表的基础题吃透344反转字符串、125验证回文串、387字符串中的第一个唯一字符、242有效的字母异位词、49字母异位词分组。这个阶段目标是熟悉字符串作为字符数组的基本操作把相向指针、频次统计练成肌肉记忆。第二阶段主攻滑动窗口3无重复字符的最长子串、76最小覆盖子串、567字符串的排列、438找到字符串中所有字母异位词。这几题套路一致能放在一起对比总结是性价比最高的一个阶段。第三阶段进入动态规划和匹配算法5最长回文子串、1143最长公共子序列、72编辑距离、28找出字符串中第一个匹配项的下标KMP。动态规划的字符串题变化最多但核心套路就是二维DP和状态转移建议把每个题的dp表都亲手画一遍。第四阶段处理综合题和细节题151反转字符串中的单词、8字符串转换整数、179最大数、43字符串相乘。这些题不一定需要多高深的算法但边界条件多是锻炼代码严谨度的最佳材料。每天刷的题量不用多一天2到3道足够了但每道题都要按“暴力解–优化解–看题解最优解”的顺序过一遍。特别是字符串题暴力解能帮你理解题目的约束条件优化解能帮你建立“这个信息可以复用”的感觉看最优解则是在拓宽思路。5.2 常见问题与排查技巧速查表我把刷字符串题常遇到的Bug整理成了表可以直接当排查清单用。症状可能原因排查思路越界访问双指针移动前没检查left right在访问s[left]前确保left在范围内结果比预期短滑动窗口收缩条件写错把可行解给丢掉了检查收缩时是否用while判断窗口是否仍然满足条件结果比预期长没有及时更新答案或只在扩展right时更新确认答案是在哪一步取max/min异位词统计出错用字符串拼接数字做key产生歧义改用数组序列化加分隔符或直接用排序后的字符串大小写不敏感题WA忘了先把两个串都转成小写再比较预处理阶段统一调用tolowerKMP死循环next数组构建时while里没有最终出口在j next[j-1]后加if (j 0) break;动态规划结果偏大初始化时dp[0][j]和dp[i][0]填错把空字符串对应的行和列单独验证C sort崩溃比较器不满足严格弱序自定义比较器里只做确定性的return a b;调试技巧方面字符串题最推荐的方法是打印中间状态。写滑动窗口的时候在每次left和right变化后打印窗口内字符和当前记录值。写DP的时候打印整个dp表。很多WA你盯着代码看半小时看不出来一打印立刻发现是某一行的初始化问题。还有一个通用的小技巧针对字符串题可以写一个“简化版测试用例”来自查。比如滑动窗口相关题用aa、ab、空字符串、单字符字符串这四类最短用例先跑通再跑大数据量测试。空字符串、单个字符这些边界在字符串题里出现概率极高却经常被忽略。另外我习惯在写完代码之后顺手把题目给的示例输入和输出作为注释放在代码附近。因为力扣的样例往往就覆盖了最常见的那几个边界情况做题时总看样例调起Bug来心里有数。5.3 从刷题到面试字符串题的答题节奏最后说一下实战节奏。笔试或面试遇到一道字符串题不要上来就写代码先按三步走第一步确认字符集和大小写要求比如面试官说“假设只有英文字母”或“区分大小写吗”这两个问题直接决定你后面用数组还是用哈希表以及要不要做预处理转换。第二步说思路从暴力解说起再提出优化这样可以展示你的思维路径。第三步动手实现边写边把边界情况说出来比如“这里left要小于right才能继续”“这里如果ch不在A-Z范围内就直接保留”。其实很多人会忽略一个潜规则面试官考察的往往不是你背了多难的算法而是看你面对边界条件时是否反应迅速。字符串题的边界条件几乎都是明牌比如空串、首尾字符、连续分隔符、大小写混排。你如果能提前想到并把它们写进测试用例里就已经能打败不少竞争者了。我个人刷下来最深的感受是字符串题是所有算法题里“性价比”最高的一类。它的解法套路少但延展性强双指针、滑动窗口、哈希、DP、KMP、回溯都能在字符串上找到典型题目。一份题单刷两遍你收获的不只是几十道题的答案而是一整套处理“有序序列匹配与变换”问题的思维方式。这种思维不只在面试里有用日常写代码做文本处理、日志解析、规则匹配的时候也处处都有它的影子。所以如果你现在还在为字符串题发愁别焦虑按套路分阶段刷把每个模板题吃透最多一个月就能看到明显的质变。
力扣字符串题核心套路：双指针、滑动窗口、哈希表与动态规划
字符串题在力扣里出现的频率只要刷过两周的人应该都有体会说它是半壁江山不算夸张哪怕保守点把数组、动态规划也算进去字符串依然是绕不过去的那一道坎。很多人一看到字符串就觉得是“背函数”什么split、reverse、toLowerCase调完就AC真遇到卡人的题就懵。我之前也这么想过直到刷了大几十道字符串题之后才意识到字符串题真正考的东西其实很统一就三样双指针、哈希表、动态规划再加一个KMP偶尔出来吓唬人。这篇文章我就围绕这几个方向结合我在力扣上刷过的经典题目把字符串题从套路到实战完整梳理一遍适合刚开始刷题的人打基础也适合刷了一定数量但总是差临门一脚的同学整理思路。1. 先把话说清楚字符串题到底在考什么1.1 字符串的本质是“带性格的字符数组”字符串在底层就是字符数组这是理解所有字符串题的第一性原则。在C/C里是char[]或以\0结尾的字符序列在Java里是char[]加不可变封装在Python里是str不可变对象。但不管语言怎么封装抽象层面你要时刻把它当成一个有序的、可索引的字符序列来处理。这个“有序可索引”意味着什么意味着你在数组题里用过的一切技巧双指针、二分、前缀和、差分、单调栈理论上都能搬到字符串上来。比如力扣344题“反转字符串”它本质上就是数组反转双指针从两端往中间走交换字符一行思路都不用改。再比如力扣28题“找出字符串中第一个匹配项的下标”本质就是在一个数组里找子数组的匹配位置只是把数字换成了字符。但字符串也有自己的“性格”主要体现在三点。第一字符的取值空间有限。数字可以是任意大小但字符一般就是ASCII的128个或扩展的256个或者Unicode的几万个。有限取值空间意味着你经常会用一个长度为128或256的数组来当哈希表用这比用HashMap快得多。第二字符串有“字典序”这种天然的比较规则所以排序题在字符串里特别多比如力扣179题“最大数”表面是排序实际是自定义比较器的事。第三字符串拼接和切分的成本往往不是O(1)的尤其在Java和Python这类不可变字符串的语言里频繁拼接会产生大量中间对象这也是很多字符串题优化空间的来源。1.2 字符串题的五种常见“包装”字符串题之所以看着杂是因为同样一个底层考点它可以打扮成各种样子来考你。我刷了这么多道整理了五种最常见的“包装”。第一种是回文类。回文串就是正着读倒着读一样的字符串比如aba、abba。这类题的核心考点是双指针或中心扩展经典题有力扣125“验证回文串”、力扣5“最长回文子串”、力扣647“回文子串”数量。第二种是子串/子序列类。子串是连续的子序列可以跳着取。连续子串的问题十有八九用滑动窗口不连续的子序列问题基本都靠动态规划。经典题有力扣3“无重复字符的最长子串”、力扣76“最小覆盖子串”、力扣1143“最长公共子序列”。第三种是匹配/查找类。在一个长串里找一个模式串是否出现或者找第一个出现位置。这类最简单的是暴力匹配进阶是KMP、Boyer-Moore、Sunday这些字符串匹配算法。力扣28题是标准入口。第四种是变形/转换类。比如大小写转换、字符串转数字、压缩解压、反转单词等。这类题往往看起来简单但坑很多。力扣8题“字符串转换整数(atoi)”就是典型的看似简单却能把你绕晕的题各种空格、正负号、越界、非法字符的边界条件能把人磨疯。第五种是组合构造类。比如电话号码的字母组合、括号生成、分割回文串等基本是回溯/DFS的舞台字符串只是作为结果展示的载体。一旦你能把一道新题拆解成“包装 核心考点”刷题效率会高很多遇到没见过的题也不会慌。下面我就按核心考点来展开这些才是真正要背下来、练熟的东西。2. 字符串题的三板斧双指针、滑动窗口、哈希表2.1 双指针从两边逼近还是从同向出发双指针在字符串里有两个流派相向指针和同向指针。相向指针通常用于回文串、反转类题目一个指针在头一个指针在尾按条件向中间移动。同向指针就是两个指针都从左边出发一个快一个慢实际上这就是滑动窗口的基础形态。力扣344“反转字符串”是相向指针最简单也最典型的题void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } }力扣125“验证回文串”同样是相向指针但多了一个细节只考虑字母和数字且忽略大小写。于是你需要在指针移动的时候跳过非字母数字字符再统一转成小写来比较。很多人在这种“跳过比较”的组合上犯错跳过之后忘记检查left right导致越界。这是相向指针最容易踩的坑。再进阶一点是力扣345“反转字符串中的元音字母”。这题的思路和反转字符串完全一样只不过交换的条件变成了“当前指针指向的是元音字母”。注意题目里元音字母是包含大小写的aeiouAEIOU少写一个就出Bug。同向双指针我放在滑动窗口里一起讲因为它们其实是同一个东西。但这里要竖一个观点双指针不只是用来降低复杂度的更重要的是它能帮你把“涉及区间”的题目想清楚边界。每次移动left或right的时候你要在心里明确当前区间[left, right]代表什么代表什么字符集合这样的区间是否合法。想不清楚边界刷十道题错十道。2.2 滑动窗口最长子串的万能钥匙滑动窗口解决的是一类经典问题连续子串/子数组求满足某条件的最长或最短长度。它之所以高效是因为每个字符最多被left和right各访问一次时间复杂度O(n)。拿力扣3“无重复字符的最长子串”来说这是滑动窗口的入门题但它是后面一大堆难题的母题。核心思路right指针不断向右扩展把新字符加入窗口如果发现窗口中已经有重复字符就移动left指针缩小窗口直到没有重复为止。怎么判断有没有重复哈希表或长度为128的数组记录字符最后一次出现的位置。int lengthOfLongestSubstring(string s) { vectorint last(128, -1); int left 0, ans 0; for (int right 0; right s.size(); right) { if (last[s[right]] left) { left last[s[right]] 1; } last[s[right]] right; ans max(ans, right - left 1); } return ans; }这里有个非常关键的点if (last[s[right]] left)。为什么不是if (last[s[right]] ! -1)因为last数组里存的是字符上一次出现的位置但这个位置可能已经在窗口之外了。如果它出现在left之前说明虽然这个字符之前出现过但已经不属于当前窗口不影响我们。只有上一次出现位置在窗口内即 left才真正造成重复。这个细节我当初看题解时想了很久画了好几遍窗口才彻底明白。力扣76“最小覆盖子串”是滑动窗口的进阶题也是我当年刷到“怀疑人生”的题。它要求找出s中包含t所有字符的最短子串。做法是先统计t中每个字符的需求量然后right扩展找可行解再移动left找最优解同时维护一个valid变量表示当前窗口中有多少个字符已经满足了需求。这个过程里你要时刻更新valid而且在收缩窗口的时候注意检查收缩后的窗口是否仍然满足条件不满足就继续扩展right。这个题可以说是检验滑动窗口是否真正理解的分水岭能把76题自己写出来滑动窗口基本就过关了。2.3 哈希表异位词和频次统计的利器哈希表在字符串里的角色是“频次统计”和“快速查找”。力扣242“有效的字母异位词”是最基本的统计两个字符串中各字符出现的次数完全相等就是异位词。由于只有小写字母可以直接用长度为26的数组根本不需要哈希表。力扣49“字母异位词分组”稍微升级一点给定一组字符串把异位词分到同一组。核心在于“如何定义异位词的键”。两个常见做法一是把每个字符串排序后作为键因为异位词排序后结果是相同的二是统计每个字符串中26个字母的出现次数序列化成一个数组或字符串作为键。用排序法代码最简单vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring mp; for (string s : strs) { string key s; sort(key.begin(), key.end()); mp[key].push_back(s); } vectorvectorstring ans; for (auto p : mp) ans.push_back(p.second); return ans; }这里我踩过一个坑用排序后的字符串当key没问题但如果你把key定义成“字符出现次数拼接的字符串”要小心数字的歧义。比如12到底是“1个a2个b”还是“12个a”所以正确的做法是用带分隔符的序列化或者直接用一个引用计数为0的数组加自定义哈希函数。这类序列化细节在面试里很爱被追问平时刷题就要注意。哈希表还有一个高频场景是“找两个字符串的公共字符”“字符串中第一个唯一字符”力扣387之类。核心无非是先扫一遍记录频次再扫一遍按条件找答案。这类题不难但有一个共通的优化点能用数组就不要用unordered_map尤其在字符集有限ASCII的情况下数组的访问是O(1)且常数极小而unordered_map每次操作都有哈希计算和潜在的冲突处理成本。力扣上很多字符串题的题解区都在强调这一点。3. 高频经典题实战拆解从暴力到最优3.1 “最长回文子串”的三种做法对比力扣5“最长回文子串”是字符串题里的常青树解法多到可以写一篇论文。先把三种主流做法对比清楚你才能理解为什么推荐中心扩展。第一种是暴力枚举所有子串逐一判断是否回文。时间复杂度O(n^3)基本只适合用来验证小数据。第二种是动态规划定义dp[i][j]表示s[i..j]是否为回文串转移方程是dp[i][j] (s[i] s[j]) dp[i1][j-1]注意要从短的子串向长的子串递推时间复杂度O(n^2)空间也是O(n^2)。第三种是中心扩展法遍历每个中心包含单字符中心和对双字符中心两种情况向左右扩展统计每次扩展的最大长度时间复杂度O(n^2)但空间O(1)。我第一次写这题用的是动态规划后来发现中心扩展代码更简洁直观string longestPalindrome(string s) { int n s.size(); auto expand [](int l, int r) { while (l 0 r n s[l] s[r]) { l--; r; } return r - l - 1; }; int start 0, maxLen 0; for (int i 0; i n; i) { int len1 expand(i, i); int len2 expand(i, i 1); int len max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } len max(len1, len2); } return s.substr(start, maxLen); }中心扩展的启动位置计算是个容易写错的地方。如果回文串长度为奇数中心是s[i]长度为偶数中心在s[i]和s[i1]之间。算start时用的是i - (len - 1) / 2因为len是从中心向两边扩展的总长度。这个公式我建议直接记住现场推容易在边界上翻车。还有一个更高阶的算法叫Manacher马拉车复杂度O(n)。它通过在字符之间插入特殊符号如#把奇数长度和偶数长度的回文串统一成奇数长度处理同时利用已计算的回文半径数组加速。说实话我在面试里从来没有被要求手写Manacher但理解它的思想对加深“以中心扩展为原型、利用对称性优化”这件事很有帮助。如果你有时间可以看一遍Manacher并手写一遍对自信心的建立很有帮助。3.2 字符串匹配KMP算法的前因后果力扣28题“找出字符串中第一个匹配项的下标”是最经典的字符串匹配入口。暴力做法是从原串的每个位置开始尝试匹配模式串一旦失配就回退到下一个位置重来。最坏情况时间复杂度O(mn)比如s全是aaaaaaaab模式串是aaaab每匹配到最后一个字符就失配然后从头再来非常浪费。KMP算法的核心思想是在失配的时候不把匹配位置回退到模式串的开头而是利用已经匹配的前后缀信息跳到下一个可能匹配的位置。这个“前后缀信息”就是next数组。next[i]表示模式串的前缀子串p[0..i]中最长相等前后缀的长度。举个例子模式串ababc对子串abab来说最长相等前后缀是ab长度2。构建next数组的代码是KMP最绕的一部分我直接给出常用的写法vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) j; next[i] j; } return next; }这段代码的精髓在于while (j 0 p[i] ! p[j]) j next[j - 1];它其实是在递归失败时利用已有的next信息来缩短回退距离。理解这一行KMP就成功了一半。匹配阶段类似遍历主串s当字符匹配不上时沿着next回退模式串指针j直到重新匹配或j归零。这里要特别提示KMP并不是工程中最常用的字符串匹配算法因为大多数语言的indexOf、find底层用的是优化过的双端匹配算法如Boyer-Moore变体。但KMP在算法面试里是“理解层次”的题它考察的是你有没有真正理解“利用已匹配信息避免重复比较”这个思想。所以就算你只是准备面试也应该至少能默写一遍buildNext和匹配主循环。3.3 从公共子序列到编辑距离二维DP的反复应用字符串的动态规划题十有八九是二维DPdp[i][j]表示“第一个串的前i个字符”和“第二个串的前j个字符”作为子问题的答案。力扣1143“最长公共子序列”就是最基础的二维DP模板。定义dp[i][j]为text1[0..i-1]和text2[0..j-1]的最长公共子序列长度。转移时如果当前两个字符相等dp[i][j] dp[i-1][j-1] 1如果不相等则是max(dp[i-1][j], dp[i][j-1])。这里的“删掉一个字符看剩余”的思考方式是后续所有字符串DP的基础。力扣72“编辑距离”是二维DP的另一座高山。这题的dp[i][j]表示把word1[0..i-1]转换成word2[0..j-1]所需的最小操作数。操作有插入、删除、替换三种。转移方程是如果 word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] 否则: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])这三个选项分别对应删除、插入、替换。我学这题的时候最大困惑在于“为什么删除和插入是对称的”。后来想明白了dp[i-1][j]表示删掉word1当前字符然后继续转换dp[i][j-1]表示在word1当前位置插入一个和word2当前字符一样的字符然后继续转换。一个是删原串一个是补目标串本质上都是“让当前字符对齐”。字符串DP题有一个通用套路先画出二维表手动填几行数你会发现填表逻辑非常直观。很多人在没画表之前看转移方程觉得天书画过一遍之后就觉得“不过如此”。所以你在刷这类题的时候强烈建议在纸上把dp表的前几行自己填一遍比如horse转ros的编辑距离填完你就能理解为什么初始化时第一行和第一列是递增的。4. 容易被问爆的进阶套路排序、分割、大小写转换4.1 字符串排序与比较的隐藏细节字符串排序看起来简单sort(strs.begin(), strs.end())就完事了但实际场景里坑很多。第一个坑是大小写是否敏感。默认的字典序比较中大写字母的ASCII码小于小写字母A是65a是97所以Apple会排在banana前面。如果需求是“忽略大小写排序”你需要自定义比较器把每个字符先tolower再比较。第二个坑是自然排序。对file10和file2字典序排序会得到file10在前因为比较到第5个字符时1比2小。但人类通常期望file2排在file10前面这就是自然排序。力扣179题“最大数”其实也是排序比较器问题把数字转成字符串然后按照“abvsba”的字典序来比较。比如3和30拼接成330和303很明显330更大所以3应该排在30前面。这种自定义比较器的方法是字符串题的一个高频考点我单独强调一下。第三个坑是比较器的严格弱序。C的sort要求比较器必须满足“严格弱序”如果你写的比较函数返回结果不稳定比如a b和b a对同样的输入某一次同时返回true就会导致未定义行为轻则排序乱掉重则直接崩溃。所以自定义比较器时要用return a b b a;这种确定性写法不要在里面搞随机或可变状态。4.2 字符串分割与拼接的边界问题分割字符串在笔试和面试里几乎是必出现的基础操作尤其是在处理命令行参数、CSV、IP地址等场景。力扣没有专门的分割题但它藏在大量题目里比如“翻转字符串里的单词”力扣151。分割最常见的问题是连续分隔符和首尾分隔符。C里如果用istringstream默认会忽略空白字符所以多个空格会被当成一个分隔符处理而如果手动遍历按 分割就要自己跳过连续的空格。Java的split默认会丢弃尾部的空字符串但在某些版本里正则表达式需要小心Python的split()不传参数时会自动处理多个空格。这些语言差异考试和面试时必须心里有数。拼接字符串也有性能坑。在Java和Python中字符串是不可变的每一次拼接都会创建一个新对象。如果在一个循环里拼接大量字符串时间开销会很大。Java里应该用StringBuilderPython里更推荐把片段加入列表最后用.join(list)。这个优化在数据规模小的时候无所谓但力扣的测试数据经常会卡常数养成好习惯能省很多不必要的麻烦。4.3 大小写转换的“坑”不是所有字符都有大小写大小写转换在很多人眼里是无脑操作但力扣709题“转换成小写字母”就设置了陷阱题目要求实现一个函数将字符串转换为小写字母但字符串中可能包含数字、标点、非英文字符。错误做法是直接把每个字符减32这样会把5变成\u0015这种控制符。正确做法是先判断字符是否在A到Z范围内只有大写字母才减32。同理ñ、ß这种非ASCII字符不同语言的toLowerCase处理方式也不一样最好明确题目要求。这条经验延伸到更广的场景任何时候你要对字符做数学加减都要先确认它满足你假设的范围是英文字母、是数字、是ASCII还是UTF-8。我在写力扣8“字符串转换整数(atoi)”的时候就因为没有先判断字符是否为数字就贸然做c - 0结果调试了半天。这种问题不难但极其考验细心程度。5. 刷题路线与排坑手册5.1 力扣字符串题单的正确刷法很多人问字符串题从哪开始刷我的建议是不要按题号顺序刷而是按套路刷。第一阶段把双指针和哈希表的基础题吃透344反转字符串、125验证回文串、387字符串中的第一个唯一字符、242有效的字母异位词、49字母异位词分组。这个阶段目标是熟悉字符串作为字符数组的基本操作把相向指针、频次统计练成肌肉记忆。第二阶段主攻滑动窗口3无重复字符的最长子串、76最小覆盖子串、567字符串的排列、438找到字符串中所有字母异位词。这几题套路一致能放在一起对比总结是性价比最高的一个阶段。第三阶段进入动态规划和匹配算法5最长回文子串、1143最长公共子序列、72编辑距离、28找出字符串中第一个匹配项的下标KMP。动态规划的字符串题变化最多但核心套路就是二维DP和状态转移建议把每个题的dp表都亲手画一遍。第四阶段处理综合题和细节题151反转字符串中的单词、8字符串转换整数、179最大数、43字符串相乘。这些题不一定需要多高深的算法但边界条件多是锻炼代码严谨度的最佳材料。每天刷的题量不用多一天2到3道足够了但每道题都要按“暴力解–优化解–看题解最优解”的顺序过一遍。特别是字符串题暴力解能帮你理解题目的约束条件优化解能帮你建立“这个信息可以复用”的感觉看最优解则是在拓宽思路。5.2 常见问题与排查技巧速查表我把刷字符串题常遇到的Bug整理成了表可以直接当排查清单用。症状可能原因排查思路越界访问双指针移动前没检查left right在访问s[left]前确保left在范围内结果比预期短滑动窗口收缩条件写错把可行解给丢掉了检查收缩时是否用while判断窗口是否仍然满足条件结果比预期长没有及时更新答案或只在扩展right时更新确认答案是在哪一步取max/min异位词统计出错用字符串拼接数字做key产生歧义改用数组序列化加分隔符或直接用排序后的字符串大小写不敏感题WA忘了先把两个串都转成小写再比较预处理阶段统一调用tolowerKMP死循环next数组构建时while里没有最终出口在j next[j-1]后加if (j 0) break;动态规划结果偏大初始化时dp[0][j]和dp[i][0]填错把空字符串对应的行和列单独验证C sort崩溃比较器不满足严格弱序自定义比较器里只做确定性的return a b;调试技巧方面字符串题最推荐的方法是打印中间状态。写滑动窗口的时候在每次left和right变化后打印窗口内字符和当前记录值。写DP的时候打印整个dp表。很多WA你盯着代码看半小时看不出来一打印立刻发现是某一行的初始化问题。还有一个通用的小技巧针对字符串题可以写一个“简化版测试用例”来自查。比如滑动窗口相关题用aa、ab、空字符串、单字符字符串这四类最短用例先跑通再跑大数据量测试。空字符串、单个字符这些边界在字符串题里出现概率极高却经常被忽略。另外我习惯在写完代码之后顺手把题目给的示例输入和输出作为注释放在代码附近。因为力扣的样例往往就覆盖了最常见的那几个边界情况做题时总看样例调起Bug来心里有数。5.3 从刷题到面试字符串题的答题节奏最后说一下实战节奏。笔试或面试遇到一道字符串题不要上来就写代码先按三步走第一步确认字符集和大小写要求比如面试官说“假设只有英文字母”或“区分大小写吗”这两个问题直接决定你后面用数组还是用哈希表以及要不要做预处理转换。第二步说思路从暴力解说起再提出优化这样可以展示你的思维路径。第三步动手实现边写边把边界情况说出来比如“这里left要小于right才能继续”“这里如果ch不在A-Z范围内就直接保留”。其实很多人会忽略一个潜规则面试官考察的往往不是你背了多难的算法而是看你面对边界条件时是否反应迅速。字符串题的边界条件几乎都是明牌比如空串、首尾字符、连续分隔符、大小写混排。你如果能提前想到并把它们写进测试用例里就已经能打败不少竞争者了。我个人刷下来最深的感受是字符串题是所有算法题里“性价比”最高的一类。它的解法套路少但延展性强双指针、滑动窗口、哈希、DP、KMP、回溯都能在字符串上找到典型题目。一份题单刷两遍你收获的不只是几十道题的答案而是一整套处理“有序序列匹配与变换”问题的思维方式。这种思维不只在面试里有用日常写代码做文本处理、日志解析、规则匹配的时候也处处都有它的影子。所以如果你现在还在为字符串题发愁别焦虑按套路分阶段刷把每个模板题吃透最多一个月就能看到明显的质变。
