5. 最长回文子串(较难)
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
思路1：
暴力求解，这里会超时，时间复杂度o(n^3)
说明：暴力解法时间复杂度高，但是思路清晰、编写简单。由于编写正确性的可能性很大，可以使用暴力匹配算法检验我们编写的其它算法是否正确。优化的解法在很多时候，是基于“暴力解法”，以空间换时间得到的，因此思考清楚暴力解法，分析其缺点，很多时候能为我们打开思路。
参考代码 1：Java 代码正常运行，C++ 代码超出内存限制，Python 代码超时。
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
思路2
方法二：中心扩展算法
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
思路3
动态规划
“动态规划”最关键的步骤是想清楚“状态如何转移”，事实上，“回文”是天然具有“状态转移”性质的：
一个回文去掉两头以后，剩下的部分依然是回文（这里暂不讨论边界）。
依然从回文串的定义展开讨论：
1、如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；
2、如果一个字符串的头尾两个字符相等，才有必要继续判断下去。
（1）如果里面的子串是回文，整体就是回文串；
（2）如果里面的子串不是回文串，整体就不是回文串。
即在头尾字符相等的情况下，里面子串的回文性质据定了整个子串的回文性质，这就是状态转移。因此可以把“状态”定义为原字符串的一个子串是否为回文子串。
状态转移方程如下
$$
P(i, j)={ \text { true } \text { s[i,j] 是回文串 } \ \text { false } \mathrm{s}[\mathrm{i}, \mathrm{j}] \text { 不是回文串 }
$$
$$
P(i, j)=(P(i+1, j-1) & & S[i]==S[j])
$$
本思路代码见代码3
本思路中时间复杂度为o(n^2),空间复杂度为o(n^2),，其中空间可以优化为o(n)—–未写
代码1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public String longestPalindrome(String s) {
return subString(s);
}
public static String subString(String s){
int max = 0;
String maxstring = "";
for(int i=0;i<s.length();i++){
for(int j=i+1;j<=s.length();j++){
String s1 = s.substring(i,j);
if(s1.length()>max && huiwen(s1)){
max = Math.max(max,s1.length());
maxstring = s1;
}
}
}
return maxstring;
}
public static boolean huiwen(String s){
int len = s.length();
for(int i=0;i<len/2;i++){
if(s.charAt(i)!=s.charAt(s.length()-i-1)){
return false;
}
}
return true;
}
}
|
代码2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public String longestPalindrome(String s) {
if(s.length()<2){
return s;
}
int maxlen = 0;
String maxstr = "";
for(int i=0;i<s.length()-1;i++){
String str1 = Judge(s,i,i);
String str2 = Judge(s,i,i+1);
String maxstr1 = str1.length()>str2.length()?str1:str2;
if(maxstr1.length()>maxlen){
maxstr = maxstr1;
maxlen = maxstr1.length();
}
}
return maxstr;
}
String Judge(String s,int left,int right){
while(left>=0 && right<s.length()){
if(s.charAt(left)==s.charAt(right)){
left--;
right++;
}
else {
break;
}
}
return s.substring(left+1,right);
}
}
|
代码3：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public String longestPalindrome(String s) {
int len = s.length();
String res ="";
boolean[][] dp = new boolean[len][len];
for(int i=len-1;i>=0;i--){
for(int j=i;j<len;j++){
if(s.charAt(i)==s.charAt(j)){
dp[i][j]=j-i<2?true:dp[i+1][j-1];
}else{
dp[i][j]=false;
}
if(j-i+1>res.length() && dp[i][j]){
res = s.substring(i,j+1);
}
}
}
return res;
}
}
|