知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 08 - 最长回文子串 ## 题目(LeetCode 5) 给定字符串 s,找到最长的回文子串。 ``` 输入:"babad" → 输出:"bab" 或 "aba" 输入:"cbbd" → 输出:"bb" ``` ## 先搞清楚:回文子串 vs 回文子序列 ``` 回文子串(Substring):必须连续 "babad" 的回文子串:b, a, b, a, d, bab, aba 最长回文子串:bab 或 aba(长度 3) 回文子序列(Subsequence):不要求连续 "babad" 的回文子序列:b, a, bab, aba, baab, ... 最长回文子序列:baab 或 abba(长度 4) 本题求的是回文子串(连续的) ``` ## 解法一:中心扩展(最直观) ### 大白话理解 回文串是从中心向两边对称的。枚举每个可能的中心,向两边扩展,直到不对称为止。 ``` "babad" 以 b(0) 为中心:b → 长度 1 以 a(1) 为中心:a → 扩展 → b_a_b → "bab" 长度 3 以 b(2) 为中心:b → 扩展 → a_b_a → "aba" 长度 3 以 a(3) 为中心:a → 扩展 → b_a_d → b≠d,停止 → 长度 1 以 d(4) 为中心:d → 长度 1 注意:回文串有奇数长度(中心是一个字符)和偶数长度(中心是两个字符之间) 奇数:a, bab, aba 偶数:bb(中心在两个 b 之间) ``` ### 手动模拟 "cbbd" ``` 奇数中心: 以 c(0) 为中心:c → 长度 1 以 b(1) 为中心:b → 扩展 → c_b_b → c≠b,停止 → 长度 1 以 b(2) 为中心:b → 扩展 → b_b_d → b≠d,停止 → 长度 1 以 d(3) 为中心:d → 长度 1 偶数中心(中心在相邻两字符之间): c|b:c≠b,长度 0 b|b:b==b → 扩展 → c_bb_d → c≠d,停止 → "bb" 长度 2 ← 最长 b|d:b≠d,长度 0 最长回文子串 = "bb",长度 2 ✓ ``` ### 代码 ```java public String longestPalindrome(String s) { int start = 0, maxLen = 0; for (int i = 0; i < s.length(); i++) { int len1 = expand(s, i, i); // 奇数长度,中心是一个字符 int len2 = expand(s, i, i + 1); // 偶数长度,中心是两个字符之间 int len = Math.max(len1, len2); if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; // 计算起始位置 } } return s.substring(start, start + maxLen); } private int expand(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; // 回文长度 } ``` 时间 O(n²),空间 O(1)。 ### 为什么 start = i - (len-1)/2? ``` 以 i 为中心,扩展后长度为 len 奇数长度 len=5:中心在 i,左边 2 个,右边 2 个 start = i - 2 = i - (5-1)/2 = i - 2 ✓ 偶数长度 len=4:中心在 i 和 i+1 之间,左边 2 个,右边 2 个 start = i - 1 = i - (4-1)/2 = i - 1 ✓ ``` ## 解法二:DP ### 四步法 ``` 第 1 步:dp[i][j] = s[i..j] 是否是回文串(true/false) 第 2 步: s[i] == s[j] 且 dp[i+1][j-1] == true → dp[i][j] = true 否则 dp[i][j] = false 特殊情况:j-i <= 2 时(长度 1 或 2 或 3) 长度 1:dp[i][i] = true(单个字符一定是回文) 长度 2:dp[i][i+1] = (s[i] == s[i+1]) 长度 3:dp[i][i+2] = (s[i] == s[i+2])(中间字符不影响) 统一处理:j-i <= 2 时,只要 s[i]==s[j] 就是回文 第 3 步:dp[i][i] = true(所有单字符都是回文) 第 4 步:按长度从小到大填(先填短的,再填长的) → 因为 dp[i][j] 依赖 dp[i+1][j-1](更短的子串) ``` ### 为什么 i 要从大到小遍历? ``` dp[i][j] 依赖 dp[i+1][j-1] i+1 > i,所以 i 要从大到小遍历(先算 i+1,再算 i) j-1 < j,所以 j 要从小到大遍历(先算 j-1,再算 j) 如果 i 从小到大遍历,算 dp[i][j] 时 dp[i+1][j-1] 还没算好! ``` ### 手动模拟 "babad" ``` s = "babad"(下标 0~4) 初始化(对角线全为 true): 0 1 2 3 4 b a b a d 0 b [T _ _ _ _] 1 a [ T _ _ _] 2 b [ T _ _] 3 a [ T _] 4 d [ T] 按长度 2 填(j = i+1): dp[0][1]:s[0]='b', s[1]='a',b≠a → false dp[1][2]:s[1]='a', s[2]='b',a≠b → false dp[2][3]:s[2]='b', s[3]='a',b≠a → false dp[3][4]:s[3]='a', s[4]='d',a≠d → false 按长度 3 填(j = i+2): dp[0][2]:s[0]='b', s[2]='b',相同,j-i=2≤2 → true ← "bab" 是回文 dp[1][3]:s[1]='a', s[3]='a',相同,j-i=2≤2 → true ← "aba" 是回文 dp[2][4]:s[2]='b', s[4]='d',b≠d → false 按长度 4 填(j = i+3): dp[0][3]:s[0]='b', s[3]='a',b≠a → false dp[1][4]:s[1]='a', s[4]='d',a≠d → false 按长度 5 填(j = i+4): dp[0][4]:s[0]='b', s[4]='d',b≠d → false 最终 dp 表格: 0 1 2 3 4 b a b a d 0 b [T F T F F] 1 a [ T F T F] 2 b [ T F F] 3 a [ T F] 4 d [ T] 最长回文子串:dp[0][2]=true("bab")或 dp[1][3]=true("aba"),长度 3 ✓ ``` ### 代码 ```java public String longestPalindrome(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int start = 0, maxLen = 1; for (int i = n - 1; i >= 0; i--) { // i 从大到小 for (int j = i; j < n; j++) { // j 从小到大 if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) { dp[i][j] = true; if (j - i + 1 > maxLen) { maxLen = j - i + 1; start = i; } } } } return s.substring(start, start + maxLen); } ``` 时间 O(n²),空间 O(n²)。 ## 两种解法对比 ``` 方法 时间 空间 理解难度 中心扩展 O(n²) O(1) 容易(推荐) DP O(n²) O(n²) 中等 两种时间复杂度相同,中心扩展空间更优,推荐用中心扩展。 DP 的价值在于理解区间 DP 的思路,为"最长回文子序列"等题打基础。 ``` ## 一句话总结 中心扩展最直观:枚举中心,向两边扩。DP 也行但空间 O(n²),注意 i 要从大到小遍历。 --- 上一篇:[07 - 编辑距离](./07-edit-distance.md) | 下一篇:[09 - 不同路径](./09-unique-paths.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入