文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载导读字符串是算法面试中出现频率最高的题型之一从简单的substr实现、回文判定到复杂的公共子串/子序列问题覆盖了双指针、动态规划、回溯、字典树Trie等多种核心算法。本文以 leetcode 题解仓库中的 thinkings/string-problems.en.md 为主线系统梳理字符串问题的分类框架与通用解法并结合仓库内对应题解源码深入讲解每一类问题的判定思路、状态转移与代码实现。读完本文你将掌握如何用双指针判断回文、如何用中心扩展与动态规划求解最长回文子串/子序列、如何用前缀树Trie处理前缀类问题以及如何用记忆化递归/动态规划解决单词拆分类问题。一、字符串问题的本质字符数组与算法复用字符串问题看似种类繁多但一个重要的认知是字符串本质上是字符数组。因此数组、链表等线性数据结构上沉淀下来的算法思想和技巧绝大多数都可以直接迁移到字符串问题上并且往往能发挥很好的作用。例如数组上的双指针技巧 → 回文串的判定数组上的动态规划 → 最长公共子序列、最长回文子序列、单词拆分数组上的排序与二分 → 字符串排序、字典序问题。同时字符串领域也存在一批专门为其设计的经典数据结构与算法例如前缀树Trie、马拉车算法Manacher回文半径技巧、游程编码Run-Length Encoding以及哈夫曼树Huffman Tree。本仓库的 thinkings/trie.md 对前缀树做了完整的专题讲解可作为阅读本文第 5 节的补充材料。从仓库的文件组织看字符串问题被归纳为四大类与 thinkings/string-problems.md 中文版保持一致后续章节将逐一展开实现字符串的一些原生方法回文问题前缀问题其他综合问题如单词拆分。二、第一类实现字符串的原生方法这类题目是字符串问题中最直接的一档题目歧义小、难度相对较低非常适合电面等快速考察场景重点检验基本功与代码的严谨性。代表题目包括28. implement strStr()在字符串haystack中找到子串needle首次出现的位置本质是子串匹配问题朴素实现即双循环暴力匹配进阶可延伸至 KMP 算法344. 反转字符串原地反转字符数组双指针从两端向中间交换即可。这类题目的价值在于夯实基础对边界条件空串、目标串比源串更长、大小写、Unicode 字符等的处理能力往往是区分候选人代码质量的关键。三、第二类回文问题——双指针判定与扩展思想3.1 什么是回文串回文串Palindrome是指正读和反读都一样的字符串例如level、noon都是回文串。回文问题在 LeetCode 中覆盖了判断是否回文、找最长回文子串、找最长回文子序列、分割成回文子串等由浅入深的多个层次。3.2 判定回文的通用方法头尾双指针判断一个字符串是否为回文最通用的方法是首尾双指针左指针从头部、右指针从尾部向中间移动逐字符比较一旦遇到不相等即可判定非回文直到两指针相遇。以仓库题解 problems/125.valid-palindrome.md验证回文串为例该题要求只考虑字母和数字字符忽略大小写并将空字符串定义为有效回文。其 JS 实现如下function isValid(c) { const charCode c.charCodeAt(0); const isDigit charCode 0.charCodeAt(0) charCode 9.charCodeAt(0); const isChar charCode a.charCodeAt(0) charCode z.charCodeAt(0); return isDigit || isChar; } var isPalindrome function (s) { s s.toLowerCase(); let left 0; let right s.length - 1; while (left right) { if (!isValid(s[left])) { left; continue; } // 跳过非字母数字字符 if (!isValid(s[right])) { right--; continue; } // 跳过非字母数字字符 if (s[left] s[right]) { left; right--; } else break; // 字符不一致提前终止 } return right left; };实现中的关键点解析预处理与跳过逻辑isValid通过字符码判断是否为数字0-9或小写字母a-z配合toLowerCase()统一大小写即可在 O(1) 时间内完成单字符过滤提前终止一旦s[left] ! s[right]立即退出循环无需遍历完整个字符串判定条件循环结束后right left说明所有对应字符均相等返回true。同一份题解中还提供了 C、Python、Java 三种语言的版本。Python 版本给出了两条思路其中简洁的语言特性写法过滤出字母数字后反转比较可作为面试时的补充思路def isPalindrome2(self, s: str) - bool: s .join(i for i in s if i.isalnum()).lower() return s s[::-1]时间复杂度O(N)N 为字符串长度空间复杂度O(1)双指针写法不含过滤副本。3.3 最长回文子串扩展思想与动态规划判断是否回文只需 O(N) 的双指针但求解最长回文子串则要复杂得多。解决这类问题的核心思想是两个字——扩展extend如果在一个不是回文串的字符串两端添加任何字符或者在回文串左右分别添加不同的字符得到的一定不是回文串。换句话说回文串的判定具备由内向外的生长性一个回文串去掉首尾各一个字符后仍然是一个回文串首尾字符相等。基于这个性质我们可以建立大问题与小问题之间的关联进而构造动态规划模型。以仓库题解 problems/5.longest-palindromic-substring.md 为例定义dp[i][j]表示s中从下标i到j含两端的子串是否为回文状态转移方程即上述描述的代码化if (s[i] s[j] dp[i 1][j - 1]) { dp[i][j] true; }base case有两个单个字符i j天然是回文对称轴是字符本身两个相同字符j - i 1 s[i] s[j]也是回文对称轴是两者之间的虚拟点。完整 JS 实现自底向上、倒序遍历i因为dp[i][j]依赖dp[i 1][j - 1]var longestPalindrome function (s) { if (!s || s.length 0) return ; let res s[0]; const dp []; for (let i s.length - 1; i 0; i--) { dp[i] []; for (let j i; j s.length; j) { if (j - i 0) dp[i][j] true; // base case 1单字符 else if (j - i 1 s[i] s[j]) dp[i][j] true; // base case 2双字符 else if (s[i] s[j] dp[i 1][j - 1]) { // 状态转移 dp[i][j] true; } if (dp[i][j] j - i 1 res.length) { res s.slice(i, j 1); // 更新最长结果 } } } return res; };仓库中同时提供了 Python 的中心扩展法实现对每个位置分别向左右扩展奇数长度与偶数长度回文取最长者与 C 版本class Solution: def longestPalindrome(self, s: str) - str: n len(s) if n 0: return res s[0] def extend(i, j, s): while(i 0 and j len(s) and s[i] s[j]): i - 1 j 1 return s[i 1:j] for i in range(n - 1): e1 extend(i, i, s) # 奇数长度回文对称轴为字符本身 e2 extend(i, i 1, s) # 偶数长度回文对称轴为两字符之间 if max(len(e1), len(e2)) len(res): res e1 if len(e1) len(e2) else e2 return res时间复杂度O(N²)DP 与中心扩展均为两重循环空间复杂度DP 为 O(N²)二维状态表中心扩展为 O(1)仅常数空间记录结果。3.4 最长回文子序列动态规划的状态取舍子串要求连续而子序列允许跳过字符因此最长回文子序列无法直接沿用子串的判定方法但扩展思想依然成立只是状态需要区分是否选择两端字符。仓库题解 problems/516.longest-palindromic-subsequence.md 给出了清晰的状态转移if (s[i] s[j]) { dp[i][j] dp[i 1][j - 1] 2; // 两端相等回文长度 2 } else { dp[i][j] Math.max(dp[i][j - 1], dp[i 1][j]); // 两端不等取舍弃左端或右端后的较大值 }其中dp[i][j]表示s[i..j]含两端的最长回文子序列长度base case 是单字符时长度为 1。JS 完整实现var longestPalindromeSubseq function (s) { const dp []; for (let i s.length - 1; i 0; i--) { dp[i] Array(s.length).fill(0); for (let j i; j s.length; j) { if (i - j 0) dp[i][j] 1; // base case单字符 else if (s[i] s[j]) dp[i][j] dp[i 1][j - 1] 2; else dp[i][j] Math.max(dp[i][j - 1], dp[i 1][j]); } } return dp[0][s.length - 1]; };仓库还提供了 Python3 的记忆化递归版本代码更贴近状态定义的直觉class Solution: def longestPalindromeSubseq(self, s: str) - int: cache def dp(l, r): if l r: return int(l r) if s[l] s[r]: return 2 dp(l 1, r - 1) return max(dp(l 1, r), dp(l, r - 1)) return dp(0, len(s) - 1)时间复杂度O(N²)枚举全部状态空间复杂度O(N²)二维 DP 表。3.5 分割回文串回溯法求所有方案当问题从求最优值变为求所有方案时常规思路是回溯法Backtracking。仓库题解 problems/131.palindrome-partitioning.md分割回文串要求将字符串s分割成若干子串使每个子串都是回文串并返回所有可能的分割方案例如输入aab输出[[aa,b], [a,a,b]]。JS 实现核心是判断前缀回文 递归剩余部分 撤销选择function isPalindrom(s) { let left 0, right s.length - 1; while (left right s[left] s[right]) { left; right--; } return left right; } function backtrack(s, list, tempList, start) { const sliced s.slice(start); if (isPalindrom(sliced) tempList.join().length s.length) list.push([...tempList]); for (let i 0; i sliced.length; i) { const sub sliced.slice(0, i 1); if (!isPalindrom(sub)) continue; // 只对回文前缀进行分割 tempList.push(sub); backtrack(s, list, tempList, start i 1); tempList.pop(); // 回溯撤销选择 } } var partition function (s) { const list []; backtrack(s, list, [], 0); return list; };Python 版本思路一致helper(s, tmp)在s为空时记录方案否则从 1 到len(s)逐个切分前缀若s[:i]是回文则递归处理剩余部分。回溯法是组合类问题的通用模板本仓库中 problems/39.combination-sum.md、problems/46.permutations.md、problems/78.subsets.md 等题目均采用同一套路可对照学习。四、回文问题总结与延伸回文类问题的解题脉络可以概括为一张递进表问题方法复杂度时间/空间仓库题解验证回文串125首尾双指针O(N) / O(1)problems/125.valid-palindrome.md最长回文子串5中心扩展 / DPO(N²) / O(1) 或 O(N²)problems/5.longest-palindromic-substring.md最长回文子序列516动态规划O(N²) / O(N²)problems/516.longest-palindromic-subsequence.md分割回文串131回溯 回文判定指数级方案数problems/131.palindrome-partitioning.md如需进一步压榨最长回文子串的时间复杂度至 O(N)可以研究马拉车算法Manacher它充分利用回文的对称性借助回文半径数组避免大量重复比较这正是原文档中所强调的——充分利用回文的特点可以减少很多无谓的计算。更进阶的变体还包括最短回文串在字符串前面补字符使其成为回文等其本质仍是对回文对称性的运用。五、第三类前缀问题——前缀树Trie的直觉与权衡5.1 为什么需要前缀树前缀问题如求最长公共前缀、判断某字符串是否以给定前缀开头最符合直觉的数据结构是前缀树Trie字典树。其核心思想是将一组字符串按字符逐层存储到一棵多叉树上公共前缀在树中只存储一次从而把字符串查找从逐条遍历暴力 O(m × n)优化为沿树逐字符行走O(min(m, k))。关于 Trie 的完整讲解仓库在 thinkings/trie.md 中提供了详尽专题包括节点结构数据域存字符控制域可自定义如count表示以该节点结尾的单词数、preCount表示以该节点为前缀的串数、isWord标记单词结尾插入操作从根出发逐字符查找有对应子节点则更新属性没有则创建新节点查询操作逐字符下探中途缺失节点即表示不存在遍历完成后还需检查结尾节点的结束标记区分完整单词与仅前缀。原文档也客观指出了 Trie 的缺点当字符串集合的公共前缀很少时Trie 会为几乎每个字符单独建立节点内存消耗较大。因此是否选用 Trie需要结合实际数据的前缀重叠程度来权衡。5.2 实现前缀树以 208 题为例仓库题解 problems/208.implement-trie-prefix-tree.md 要求实现包含insert、search、startsWith三个操作的前缀树且输入由小写字母a-z构成。题解定义节点结构如下function TrieNode(val) { this.val val; // 当前字母 this.children []; // 仅 a-z长度最大为 26 this.isWord false; // 标记是否为某单词的结尾 } function computeIndex(c) { return c.charCodeAt(0) - a.charCodeAt(0); // 字母 → 0..25 的下标 }三个操作共享同一套从根出发逐字符找子节点的框架var Trie function () { this.root new TrieNode(null); }; Trie.prototype.insert function (word) { let ws this.root; for (let i 0; i word.length; i) { const c word[i]; const current computeIndex(c); if (!ws.children[current]) ws.children[current] new TrieNode(c); ws ws.children[current]; } ws.isWord true; // 单词末尾节点打上标记 }; Trie.prototype.search function (word) { let ws this.root; for (let i 0; i word.length; i) { const current computeIndex(word[i]); if (!ws.children[current]) return false; ws ws.children[current]; } return ws.isWord; // 必须是以该字符结尾的完整单词 }; Trie.prototype.startsWith function (prefix) { let ws this.root; for (let i 0; i prefix.length; i) { const current computeIndex(prefix[i]); if (!ws.children[current]) return false; ws ws.children[current]; } return true; // 只要能走完前缀路径即成立 };关键点search与startsWith的区别完全由isWord标记承担——search(apple)为true但search(app)为false而startsWith(app)为true。insert、search、startsWith的时间复杂度均为 O(len(key))与字典中单词总数无关这正是 Trie 空间换时间的价值所在。该题解还关联了前缀树的一系列进阶题目problems/211.add-and-search-word-data-structure-design.md支持通配符的单词搜索、problems/212.word-search-ii.md矩阵单词搜索、problems/472.concatenated-words.md连接词等适合作为专题串联练习。5.3 最长公共前缀前缀问题的朴素起点前缀类问题还有一个最朴素的代表——14. 最长公共前缀在一组字符串中找出所有字符串共有的最长前缀。朴素实现即可纵向扫描取第一个字符串为基准逐列比较其余字符串对应位置的字符遇到不一致或越界即停止。该题无需构建 Trie是 Trie 场景大量字符串反复做前缀查询之外的高性价比选择也再次印证了先评估数据规模与问题形态再决定是否引入重型数据结构的原则。六、第四类其他综合问题——以 139. 单词拆分为例字符串问题的第四类是难以简单归类但极具代表性的综合题典型如单词拆分Word Break。仓库题解 problems/139.word-break.md 要求判断给定字符串s能否由字典wordDict中的单词可重复使用拼接而成。暴力思路从匹配位置 0 开始逐个尝试wordDict中的单词若能匹配则更新匹配位置继续递归。以s leetcode、wordDict [leet, code]为例先用leet匹配剩余code继续在字典中查找并匹配成功返回true若遍历字典一轮没有任何进展则返回false。关键洞察每次成功匹配后问题规模缩小而问题性质不变——这恰好是动态规划的适用特征。题解给出的记忆化递归版本极其简洁class Solution: def wordBreak(self, s: str, wordDict: List[str]) - bool: wordDict set(wordDict) # 哈希集合化单词存在性判断 O(1) cache def dp(pos): if pos len(s): return True cur for nxt in range(pos, len(s)): cur s[nxt] if cur in wordDict and dp(nxt 1): return True return False return dp(0)var wordBreak function (s, wordDict) { const dp Array(s.length 1); dp[0] true; // 空串视为可拆分 for (let i 0; i s.length 1; i) { for (let word of wordDict) { if (word.length i dp[i - word.length]) { if (s.substring(i - word.length, i) word) { dp[i] true; } } } } return dp[s.length] || false; };优化要点将字典放入哈希集合set/unordered_set使判断子串是否在字典中降为 O(1)同时由暴力版枚举字典中每个单词改为枚举切分长度 k直接截取s[pos:posk]查集合使复杂度与字典长度m解耦。时间复杂度O(N²)N 为字符串长度空间复杂度O(m)哈希集合 DP 数组。七、总结字符串问题的分类解题框架回顾本仓库 thinkings/string-problems.en.md 建立的知识地图字符串问题可以按以下框架快速定位解法原生实现类28、344考察基本功与边界处理双指针、朴素匹配即可回文类判定用双指针求最长子串用中心扩展或 DP求最长子序列用 DP区分选/不选两端求全部分割方案用回溯追求极致性能可上马拉车算法前缀类公共前缀重叠度高、查询频繁时用前缀树Trie空间换时间单次求最长公共前缀可纵向扫描综合类如 139 单词拆分识别子问题同构特征用记忆化递归/DP 哈希集合优化。掌握上述每一类问题的代表题与状态转移模板就能在面对新的字符串题目时快速完成归类 → 选型 → 套模板 → 边界修正的完整解题流程。仓库中每道题解均提供了多语言JS / Python / C / Java实现与复杂度分析读者可直接按上述路径逐个精读形成自己的字符串专题题单。扩展阅读仓库中与字符串紧密相关的专题还包括 thinkings/dynamic-programming.md动态规划方法论、thinkings/backtrack.md回溯模板、thinkings/trie.md前缀树专题、thinkings/string-problems.md本文中文原版以及 selected/LCS.md最长公共子序列建议串联阅读。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐LeetCode 字符串问题专题回文双指针、中心扩展求最长回文子串与 Trie 前缀树实战指南LeetCode 字符串问题专题回文双指针、中心扩展求最长回文子串与 Trie 前缀树实战指南 字符串是面试与竞赛中出现频率最高的题型之一从手写 subst文档教程知识库437. 路径总和 III 题解二叉树上的前缀和与 DFS 回溯LeetCode 解题之路437. 路径总和 III 题解二叉树上的前缀和与 DFS 回溯LeetCode 解题之路 导读 本题是 LeetCode 437「路径总和 III」的完文档教程知识库LeetCode 131 Palindrome Partitioning 题解回溯、动态规划与递归四种实现基于 leetcode 仓库实战LeetCode 131 Palindrome Partitioning 题解回溯、动态规划与递归四种实现基于 leetcode 仓库实战 本文以 art示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考