5-最长回文子串

5. 最长回文子串

动态规划DP

  • 思想:对于一个子串而言,如果它是回文串,并且长度大于2,那么它首尾的两个字母去掉之后,它仍然是个回文串
  • 状态转移方程: $(s[i]==s[j])\ \&\& \ dp[i+1][j-1]$ ,$dp[i][j]$ 表示子串$s[i..j]$是否是回文
  • 边界条件,即子串的长度为 1 或 2。: $dp(i,i)=true$ 单个字符串, $dp(i,i+1) = (Si==Si+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
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
String ans="";
for(int k=0;k<n;k++){
for(int i=0;i+k<n;i++){
int j = i+k;
// 先处理两种临界情况
if(k==0) { //k=0时,j=i, dp[i][j]相当于一个字符串,一定是回文串
dp[i][j] = true;
} else if(k==1){ // k=1时,j=i+1 dp[i][j]相当于连续两个字符,相同时,一定是回文串
dp[i][j] = (s.charAt(i)==s.charAt(j));
} else{ // k>1 时,需满足状态转移方程,dp[i,j] = dp[i+1][j-1] && (si==sj)
dp[i][j] = (s.charAt(i)==s.charAt(j) && dp[i+1][j-1]);
}
if(dp[i][j] && k+1>ans.length()){ //更新回文串长度
ans = s.substring(i, i+k+1); // 注意子串方法的具体用法
}
}
}
return ans;
}
}

时间复杂度:$O(n^2)$ 其中n是字符串长度,动态规划的状态总数为$O(n^2)$,对于每个状态,我们需要转移的实际为$O(1)$

空间复杂度: $O(n^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
//中心扩展
public String longestPalindrome(String s) {
if(s==null || s.length()==0) return "";
int start = 0, end=0; // 初始化最大回文串的起点和终点
// 遍历每个位置,当做中心
for(int i=0;i<s.length();i++){
// 分别拿到奇数偶数的回文串长度
int len_odd = expandCenter(s,i,i);
int len_even = expandCenter(s,i,i+1);
int len = Math.max(len_odd,len_even);
// 计算对应最大回文子串的起点和终点
if(len > end-start){
/**
这里为什么要len-1? ,因为for循环是从0开始的,
如果是奇数回文,假设有个回文是3个,那么len=3,此时中心i是下标1(从0开始),那么(len-1)/2和len/2的结果都是1,因为整数会向下取整
但是如果是偶数回文,假设和有个回文是4个,那么len=4,此时的中心是一条虚线,但是i的位置在1,因为s是从左向右遍历的,
如果从左向右i的位置就会在2,这个时候 (len-1)/2 =1 ,len/2=2 ,很明显为了保证下标正确,我们需要的是(len-1)/2,原因是i在中心线的左边一位。
所以要少减一个1
*/
start = i-(len-1)/2;
end = i+len/2;
}
}
return s.substring(start, end+1);//注意这里end+1是因为java自带左闭右开的原因
}

private int expandCenter(String s,int left, int right){//起始的左右边界
// left = right的时候,此时回文中心是一个字符,回文串的长度是奇数
// right = left+1的时候,此时回文中心是一个空隙,回文串的长度是偶数
// 跳出循环的时候恰好满足 s.charAt(left)!=s.charAt(right)
while(left >=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
left--;
right++;
}
return right-left-1; //回文串的长度是right-left+1-2 = right -left -1
}

时间复杂度:$O(n^2)$ 其中n是字符串长度,长度为1和2的回文中心分别有n和n-1个,每个回文中心最多会向外扩展$O(n)$次

空间复杂度:$O(1)$