Interview_DS_Algo 字符串专题精讲81 道 LeetCode 字符串问题的 C 解法清单与源码剖析【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo本篇文章以Interview_DS_Algo仓库中的 strings/README.md 为骨架系统梳理该专题收录的 81 道 LeetCode 字符串问题完整继承原文档的题目总表与精读顺序并结合仓库内真实 C 源码KMP、逆向解码、频率判定、子序列、原地压缩、括号处理等逐题拆解核心思路、复杂度与代码实现。读完本文你将获得一张可直接照图刷题的全量清单以及从会写解法到能讲清楚复杂度与边界的面试级理解。一、专题概览这份字符串问题清单是什么strings/README.md 是仓库中「字符串Strings」专题的入口文档定位是A curated collection of LeetCode string challenges with clean C solutions——一份按人工精读顺序排序的 LeetCode 字符串挑战清单每题一行直接链到对应的 C 解法源码。几个关键事实均以仓库现状为准题量README 徽章标注 Problems-81即 81 道题目语言徽章标注 C 与 Java 双语言源码文件中多数题目同时给出 C 与 Java 两份实现如 Determine if Two Strings Are Close.cpp 同时包含两版平台以 LeetCode 为主部分题目同时提供 GeeksforGeeks 链接如 Knuth-Morris-Pratt KMP String Matching Algorithm.cpp 的 GfG 链接组织方式原文档明确说明Sorted in curated study order — start at the top and work down, or jump to whatever youre stuck on即表内顺序本身就是一条推荐学习路径可从头顺序刷也可按需跳转。除主表外README 还导航到两个子集合在仓库中均已确认存在子集合相对路径内容Easy Tagged易题合集strings/Easy Tagged面向电话面试的简单题含 28 个 .cpp 文件Simulation字符串模拟strings/Simulation直接按题意逐步回放过程的题目含独立 README.md此外还有第三个隐藏入口 strings/String Algorithms收录了 KMP 字符串匹配算法的完整实现是专题中最接近算法模板的文件。二、问题总表81 道题目全量清单按原始精读顺序下表完整继承自 strings/README.md所有链接已转换为仓库根目录相对路径保持原始精读顺序不变Leetcode #题目解法1638Count Substrings That Differ by One CharacterCode1657Determine if Two Strings Are CloseCode880Decoded String at IndexCode556Next Greater Element IIICode161One Edit DistanceCode1249Minimum Remove to Make Valid ParenthesesCode916Word SubsetsCode936Stamping The SequenceCode696Count Binary SubstringsCode609Find Duplicate File in SystemCode392Is SubsequenceCode165Compare Version NumbersCode151Reverse Words in a StringCode186Reverse Words in a String IICode557Reverse Words in a String IIICode43Multiply StringsCode415Add StringsCode537Complex Number MultiplicationCode848Shifting LettersCode443String CompressionCode1832Check if the Sentence Is PangramCode38Count and SayCode12Integer to RomanCode1662Check If Two String Arrays are EquivalentCode899Orderly QueueCode1544Make The String GreatCode1704Determine if String Halves Are AlikeCode520Detect CapitalCode944Delete Columns to Make SortedCode93Restore IP AddressesCode472Concatenated WordsCode28Find the Index of the First Occurrence in a StringCode859Buddy StringsCode2272Substring With Largest VarianceCode459Repeated Substring PatternCode68Text JustificationCode316, 1081Remove Duplicate LettersCode844Backspace String CompareCode1759Count Number of Homogenous SubstringsCode2785Sort Vowels in a StringCode1930Unique Length-3 Palindromic SubsequencesCode1980Find Unique Binary StringCode2947Count Beautiful Substrings ICode2949Count Beautiful Substrings IICode2147Number of Ways to Divide a Long CorridorCode1531String Compression IICode2125Number of Laser Beams in a BankCode3006Find Beautiful Indices in the Given Array ICode3008Find Beautiful Indices in the Given Array IICode3029Minimum Time to Revert Word to Initial State ICode3031Minimum Time to Revert Word to Initial State IICode3076Shortest Uncommon Substring in an ArrayCode3084Count Substrings Starting and Ending with Given CharacterCode2486Append Characters to String to Make SubsequenceCode2191Sort the Jumbled NumbersCode564Find the Closest PalindromeCode592Fraction Addition and SubtractionCode214Shortest PalindromeCode1813Sentence Similarity IIICode2938Separate Black and White BallsCode670Maximum SwapCode1233Remove Sub-Folders from the FilesystemCode3163String Compression IIICode2914Minimum Number of Changes to Make Binary String BeautifulCode2109Adding Spaces to a StringCode2825Make String a Subsequence Using Cyclic IncrementsCode2337Move Pieces to Obtain a StringCode2981, 2982Find Longest Special Substring That Occurs Thrice I IICode2182Construct String With Repeat LimitCode1769Minimum Number of Operations to Move All Balls to Each BoxCode1400Construct K Palindrome StringsCode3223Minimum Length of String After OperationsCode2375Construct Smallest Number From DI StringCode2999Count the Number of Powerful IntegersCode3403Find the Lexicographically Largest String From the Box ICode2434Using a Robot to Print the Lexicographically Smallest StringCode3234Count the Number of Substrings With Dominant OnesCode1513Number of Substrings With Only 1sCode2211Count Collisions on a RoadCode955Delete Columns to Make Sorted IICode2452Words Within Two Edits of DictionaryCode3499Maximize Active Section with Trade ICode说明316, 1081与2981, 2982两行各自对应两个 LeetCode 题号同源题合并存放在单个.cpp文件中。三、配套子集合速览3.1 Easy Tagged电话面试友好型简单题strings/Easy Tagged 收录 28 道低难度字符串题典型如 Valid Anagram、Length of Last Word、Rotate String、First Unique Character in a String、Reverse Prefix of Word 等特点是思路直白、单函数可解适合作为热身或电话面phone-interview题库。3.2 Simulation按题意逐步模拟strings/Simulation/README.md 明确给出了该子集合的定位These problems dont need a clever trick so much as faithfullyreplayingthe rules: build the matrix, apply each operation in order, and read off the answer.即这类题目不需要精巧技巧关键是忠实回放规则按顺序构造矩阵、依次执行操作、最后读出答案。共 3 题LC #题目难度解法2075Decode the Slanted CiphertextMediumCode3612Process String with Special Operations IMediumCode3614Process String with Special Operations IIHardCode3.3 String Algorithms算法模板strings/String Algorithms 目前收录一个完整算法模板Knuth-Morris-Pratt KMP String Matching Algorithm.cpp既是主表中28字符串首个匹配位置、214Shortest Palindrome、3008Find Beautiful Indices II等题目的底层支撑也是面试手写字符串匹配时的标准参考实现。四、代表性题目的源码级解读本节选取专题中覆盖不同技术范式的 8 道题逐一给出仓库真实源码、复杂度分析与边界讲解帮你建立每类题该想什么的映射。4.1 模式匹配KMP 与 LPS 数组O(mn) 替代 O(m·n)Knuth-Morris-Pratt KMP String Matching Algorithm.cpp 的文件头注释同时给出了两种思路的复杂度对比Approach-1暴力对文本的每个位置尝试匹配模式串T.C : O(m*n)S.C : O(1)Approach-2KMPT.C : O(mn)S.C : O(m)其中 m 为模式串长度。KMP 的核心是 LPSLongest Proper Prefix which is also Suffix数组lps[i]表示pattern[0..i]的最长真前缀同时也是后缀的长度。源码中computeLPS的构建逻辑KMP 文件 L21-L42void computeLPS(string pattern, vectorint lps) { int M pattern.length(); int len 0; // Length of the previous longest prefix suffix lps[0] 0; // pattern[0..0] 没有真后缀与前缀恒为 0 int i 1; while (i M) { if (pattern[i] pattern[len]) { len; lps[i] len; i; } else { if (len ! 0) { len lps[len - 1]; // 回退到上一个可复用前缀 } else { lps[i] 0; i; } } } }匹配阶段的关键在失配时的跳转而不是回溯KMP 文件 L57-L73int i 0; // 文本索引 int j 0; // 模式索引 while (i N) { if (pat[j] txt[i]) { i; j; } if (j M) { result.push_back(i - j 1); // 1-based 索引下的匹配起点 j lps[j - 1]; // 利用 LPS 复用已匹配前缀 } else if (i N pat[j] ! txt[i]) { if (j ! 0) j lps[j - 1]; // 失配不回退 i只回退 j else i; } }值得注意的实现细节result中存放的是1-based 索引i-j1若需要 0-based 只需去掉1该文件同时给出了 Java 版本两版逻辑完全一致。KMP 的价值在于文本索引i永不回退这也是它能在 O(mn) 内完成匹配的根本原因。4.2 逆向解码Decoded String at Index880Decoded String at Index.cpp 是一道典型的逆向思维题先正向累加解码长度再逆向缩小定位第 K 个字符。源码文件注释里用s leet2code3, k 15给出了非常直观的例子解码串第 15 个字符是e。核心代码C 版long long size 0; for (char ch : S) { if (isdigit(ch)) size size * (ch - 0); else size; } for (int i n - 1; i 0; i--) { K K % size; if (K 0 isalpha(S[i])) return string(1, S[i]); if (isalpha(S[i])) size--; else size size / (S[i] - 0); }关键洞察有三点正向建长度字母长度 1数字把当前长度乘以该数字size用long long防止爆 int解码串可能极长逆向收缩从末尾开始遇到数字就把总长度除以该数字相当于去掉重复块并把K对收缩后的长度取模取模定位由于每个重复块内容相同K K % size能把第 K 个位置归约到第一个重复块中的等价位置当K 0且当前字符是字母时答案就是它。这种先算总长、再逆向归约的思路与康托展开、进制转换同源面试中属于高频考察的思维模式。4.3 频率判定Determine if Two Strings Are Close1657Determine if Two Strings Are Close.cpp 标注了 Google、Microsoft、Atlassian、Morgan Stanley、Adobe、Uber 等公司标签。题目允许两种操作交换任意两个字符、变换所有出现过的某字符为另一字符次数不限。由此可得两个充要条件字符集合必须一致word1 中出现过的字符word2 中也必须出现否则无法通过变换凭空造出字符频次多重集合必须一致排序后两个 26 长度频次数组完全相等因为交换只能改变位置、变换只能重命名频次集合保持不变。源码L19-L47vectorint freq1(26), freq2(26); for (int i 0; i m; i) { freq1[word1[i] - a]; freq2[word2[i] - a]; } // 条件 1字符集合一致 for (int i 0; i 26; i) { if ((freq1[i] ! 0 freq2[i] ! 0) || (freq1[i] 0 freq2[i] 0)) continue; return false; } // 条件 2频次集合一致排序后比较 sort(begin(freq1), end(freq1)); sort(begin(freq2), end(freq2)); return freq1 freq2;复杂度T.C : O(n)排序 26 个元素是常数时间S.C : O(26) ~ O(1)。这道题的精髓在于从操作的不变量反推判定条件——这是所有判定类字符串题的通用方法论。4.4 子序列Is Subsequence392——双指针与二分的两种范式Is Subsequence.cpp 文件头注释特别说明这道题收录的原因是它可以用二分方式求解且该思路能推广到 LeetCode-792Number of Matching SubsequencesGoogle 真题这类多模式匹配场景。Approach-1二分 位置索引把t中每个字符出现的位置存进mapchar, vectorint然后对s的每个字符用upper_bound找严格大于前一个位置的最小下标mapchar, vectorint mp; for (int i 0; i t.length(); i) mp[t[i]].push_back(i); int prev -1; for (char ch : s) { if (mp.find(ch) mp.end()) return false; vectorint indices mp[ch]; auto it upper_bound(begin(indices), end(indices), prev); if (it indices.end()) return false; prev *it; // 更新为本次选中的下标 } return true;Approach-2双指针O(n) 一趟扫描i遍历tj只在匹配时前进int i 0, j 0; while (i m) { // m t.length() if (t[i] s[j]) j; i; } return j n; // 全部匹配上才为真面试要点双指针版是本题标准解二分版的价值在于单次 O(|s|·log|t|) 的预处理后对任意查询串可快速判定这是 792 题多查询场景的必备前置知识。4.5 单词反转Reverse Words in a String151——stringstream 与双指针Reverse Words in a String.cpp 标注了 Amazon、Microsoft、Adobe、Cisco、Goldman Sachs 等大量公司标签提供两种思路Approach-1stringstream利用stringstream默认以空格分词的行为把 token 逐个前插stringstream ss(s); string token, result ; while (ss token) { result token result; } return result.substr(0, result.length() - 1); // 去掉末尾多余空格Approach-2双指针原地反转三步走——先整体反转字符串再遍历把每个单词搬运到前面l, r指针维护写入位置并逐个反转单词最后substr截断L26-L63。两步都处理了任意多个空格的问题内层while跳过空格、单词搬运时在单词后补一个空格。配套题目186Reverse Words in a String II要求原地且不含多余空格是 151 的进阶版与557Reverse Words in a String III按单词逐个反转三题形成一条由易到难的完整链路。4.6 括号有效性Minimum Remove to Make Valid Parentheses1249——三种解法对比Minimum Remove to Make Valid Parentheses.cpp 标注 Facebook、Amazon、Bloomberg、Google、TikTok、Adobe且注释记录了大厂出现频率如 Facebook 111 次来源为作者自述、需自行核验。文件给出三种 O(n) 解法栈 集合用栈记录未匹配(的下标)遇空栈则标记待删结束后栈中剩余的(也标记待删最后跳过标记位置重建字符串L15-L49双向两趟扫描第一趟从左到右剔除多余的)用lastOpen计数第二趟从右到左剔除多余的(用lastClose计数再反转拼接单计数器 反向清理第一趟用open计数直接跳过open 0时的)第二趟反向跳过多余的(L108-L137。方法 3 最精简是面试中先写出朴素栈解法、再优化成单计数器的完美示范int open 0; string temp ; for (char c : s) { if (c () open; else if (c )) { if (open 0) continue; // 多余的右括号直接丢弃 open--; } temp.push_back(c); } string result ; for (int i temp.length() - 1; i 0; i--) { if (temp[i] ( open-- 0) continue; // 多余的左括号丢弃 result.push_back(temp[i]); } reverse(result.begin(), result.end()); return result;4.7 原地压缩String Compression443String Compression.cpp 是读-写双指针原地压缩的经典模板T.C : O(n)S.C : O(1)同时给出 GfG 的 Run Length Encoding 链接int i 0, index 0; while (i n) { char curr chars[i]; int count 0; while (i n chars[i] curr) { i; count; } // 统计连续段 chars[index] curr; // 写字符 if (count 1) { // 只对重复段写数字 string count_str to_string(count); for (char ch : count_str) chars[index] ch; // 数字按位写入 } } return index;要点count 1时才写数字避免a被写成a1count可能大于 9必须用to_string逐位写入。专题中1531String Compression II允许删除 k 个字符、需 DP与3163String Compression III是它的两个进阶变体三者并读可以完整覆盖压缩类题目的递进关系。4.8 暴力枚举的边界管理Count Substrings That Differ by One Character1638Count Substrings That Differ by One Character 是本专题的首题解法是三层循环枚举 差分计数核心是diff 1立即 break的剪枝for (int i 0; i m; i) { for (int j 0; j n; j) { int diff 0, k i, l j; while (k m l n) { if (s[k] ! t[l]) diff; if (diff 1) ans; // 恰好差 1 的即计入 if (diff 1) break; // 差超过 1后续不可能再恢复 l; k; } } }虽然最坏复杂度为 O(m·n·min(m,n))但diff 1的提前终止让实际开销远小于上界。它示范了字符串计数题中**枚举起点 增量维护 及时剪枝**的朴素范式适合作为专题第一题建立手感。五、按技术主题的刷题路线在保留原文档精读顺序的基础上这里按算法范式重新归并主表题目方便按需针对薄弱环节集中训练技术主题代表题目LC #双指针 / 贪心匹配392, 151, 186, 557, 844, 161, 2486, 2825, 2337, 2938, 2211字符频率 / 计数判定1657, 1832, 1704, 520, 2785, 1400, 3223, 316/1081, 2452字符串匹配算法KMP 系28, 459, 214, 3006, 3008, 3029, 3031, 2981/2982压缩 / 编码 / 大数运算443, 1531, 3163, 38, 12, 43, 415, 537, 592栈 / 单调性1249, 1544, 2434, 2375哈希 / 集合去重859, 916, 1930, 1980, 3076, 609, 472, 1233计数 / 组合数学696, 1638, 1759, 3084, 1513, 3234, 2947, 2949, 2147, 2999构造 / 贪心 / 字典序899, 564, 670, 2182, 3403, 3499, 2272, 68, 93模拟含子集合848, 1769, 2109, 2191, 944, 955, 2125, 2914, 165, 1813, 556动态规划进阶1531, 2272, 472, 2999, 2147六、如何使用本专题进行面试准备结合 strings/README.md 的组织方式与仓库源码特征给出三条可落地的使用建议首轮按原表顺序刷原文档明确将 81 题排序为 curated study order从1638开始向下推进每道题先独立写、再对照 strings 目录下同名.cpp检查复杂度注释与边界处理二轮按主题刷使用本文第五节的主题分组集中突破薄弱环节特别建议把28 / 459 / 214 / 3008与 KMP 模板 放在同一轮先背模板再做题三轮对照面试题多数源码文件头部标注了公司标签与 YouTube 讲解链接对应的题目如1249标注 Facebook/Amazon/Google、1657标注 Google/Microsoft/Adobe可作为大厂高频题重点回顾——注意公司标签属于作者自述信息使用时建议以 LeetCode 官方讨论区为准再次核验。仓库为只读学习资源所有源码可直接git clone后按需查看strings 目录下 100 个.cpp文件即本专题全部解法素材。本文基于 strings/README.md 撰写全部源码引用均来自仓库 strings 目录的真实文件。【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考