LeetCode 字符串问题专题指南：回文、前缀树与动态规划的系统化解题路径（leetcode 题解仓库实战解析）-平芜编程栈

文档
教程
知识库

【免费下载链接】leetcode

LeetCode 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）	中心扩展 / DP	O(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:pos+k]查集合"，使复杂度与字典长度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（最长公共子序列），建议串联阅读。