知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 09 - 最长回文子串 ## 题目(LeetCode 5) 给你一个字符串 s,找到 s 中最长的回文子串。 ## 解法:中心扩展 ```java class Solution { 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 l, int r) { while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; } return r - l - 1; } } ``` > 💬 **Q:这里为什么是 (len-1)/2?** > > `i` 是当前枚举的中心位置,`len` 是找到的回文串长度,`start` 是回文串的起始下标。 > > 分两种情况推导: > > **奇数长度(如 len=5,中心是 i):** > ``` > 字符串:a b c b a > 下标: 0 1 2 3 4 > ↑ i=2(中心) > > start = i - (len-1)/2 = 2 - (5-1)/2 = 2 - 2 = 0 ✓ > ``` > > **偶数长度(如 len=4,中心在 i 和 i+1 之间):** > ``` > 字符串:a b b a > 下标: 0 1 2 3 > ↑ i=1(expand 时传的是 i 和 i+1) > > start = i - (len-1)/2 = 1 - (4-1)/2 = 1 - 1 = 0 ✓ > (注意整数除法:3/2=1) > ``` > > **为什么不是 len/2?** > > 奇数长度时 `len/2` 和 `(len-1)/2` 结果一样(如 5/2=2,4/2=2)。 > 偶数长度时两者不同:`len/2 = 4/2 = 2`,但正确答案是 1。 > > 偶数回文的中心偏左(`i` 是左中心),所以左边只有 `len/2 - 1` 个字符,即 `(len-1)/2`(整数除法自动向下取整)。 > > 一句话:`(len-1)/2` 是"中心左边有多少个字符",奇偶都适用。 ## 复杂度 - 时间 O(n²),空间 O(1) ## 一句话总结 以每个字符(和每对相邻字符)为中心向两边扩展,记录最长回文。 ## 解法二:动态规划 `dp[i][j]` 表示 `s[i..j]` 是否为回文串,从短到长枚举。 ```java class Solution { public String longestPalindrome(String s) { int n = s.length(), start = 0, maxLen = 1; boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) dp[i][i] = true; for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (s.charAt(i) == s.charAt(j)) { dp[i][j] = (len == 2) || dp[i + 1][j - 1]; } if (dp[i][j] && len > maxLen) { maxLen = len; start = i; } } } return s.substring(start, start + maxLen); } } ``` ## 解法对比 | | 解法一(中心扩展) | 解法二(动态规划) | |--|--------|--------| | 时间复杂度 | O(n²) | O(n²) | | 空间复杂度 | O(1) | O(n²) | | 特点 | 空间最优,推荐 | 状态直观,可扩展到其他回文问题 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入