LeetCode5-最长回文子串-Java-动态规划

题目

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

示例 1:

1 2输入: "babad" 3输出: "bab" 4注意: "aba" 也是一个有效答案。 5 6

示例 2:

1 2输入: "cbbd" 3输出: "bb" 4

 

思路

动态规划:首先初始化一字母和二字母的回文,然后找到所有三字母回文,并依此类推…

为了改进暴力法,我们首先观察如何避免在验证回文时进行不必要的重复计算。对于 “ababa” 这个示例。如果我们已经知道 “bab” 是回文,那么很明显,“ababa” 一定是回文,因为它的左首字母和右尾字母是相同的。

回文字符串的子串也是回文,比如P[i,j](表示以i开始以j结束的子串)是回文字符串,那么P[i+1,j-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。

                          

状态转移方程:
P[i,j]=true:当且仅当P[i+1,j-1] == true && (s[i]==s[j])

 

Java代码

1class Solution { 2 public String longestPalindrome(String s) { 3 int len = s.length(); 4 if(len <= 1) 5 return s; 6 boolean[][] flag = new boolean[len][len]; 7 int start = 0; //回文串起始位置 8 int maxLen = 0; //回文串最大长度 9 // 子串长度为1和为2的初始化 10 for(int i = 0; i < len; i++){ 11 flag[i][i] = true; 12 if(i < len-1 && s.charAt(i) == s.charAt(i+1)){ 13 flag[i][i+1] = true; 14 start = i; 15 maxLen = 2 ; 16 } 17 } 18 //m代表回文子串长度,从3开始 19 for(int m = 3; m <= len; m++){ 20 for(int i = 0; i <= len-m; i++){ 21 int j = i+m-1; // 子串结束的位置 22 if(flag[i+1][j-1] && s.charAt(i)== s.charAt(j)){ 23 flag[i][j] = true; 24 start = i; 25 maxLen = m; 26 } 27 } 28 } 29 if(start == 0 && maxLen == 0) 30 return String.valueOf(s.charAt(0)); 31 return s.substring(start, start + maxLen); 32 } 33} 34

**   复杂度分析**

  • 时间复杂度:O(n^2)

  • 空间复杂度:O(n^2),该方法使用 O(n^2)的空间来存储表。

代码交流 2021