leetcode.字符串.5最长回文子串-Java

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1. 具体题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：输入: "babad"输出: "bab"

注意: "aba" 也是一个有效答案。

示例 2：输入: "cbbd"输出: "bb"

2. 思路分析

法一：暴力法

选出所有子字符串可能的开始和结束位置，并检验它是不是回文。两层 for 循环得到所有子串，对每个子串用 for 循环再判断是否为回文，所以时间复杂度为O(n^3)。会超时。

法二：动态规划

为了改进暴力法，考虑避免在验证回文时进行不必要的重复计算：若已经知道 “bab”是回文，那么“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。

3. 代码

不想写了，单纯记录下这题的思路，代码copy自windliang

public String longestPalindrome(String s) {
int length = s.length();
//用数组P[start][end]记录从start开始到end为止的子序列是否为回文序列
boolean[][] P = new boolean[length][length];
int maxDist = 0;
String maxPal = "";
for (int dist = 1; dist <= length; dist++) //遍历所有子序列的长度
for (int start = 0; start < length; start++) {
int end = start + dist - 1;
if (end >= length) //下标已经越界，结束本次循环
break;
P[start][end] = (dist == 1 || dist == 2 || P[start + 1][end - 1]) && s.charAt(start) == s.charAt(end); //长度为 1 和 2 的单独判断
if (P[start][end] && dist > maxDist) {
maxPal = s.substring(start, end + 1);
}
}
return maxPal;
}