【算法五十二】5. 最长回文子串

5. 最长回文子串动态规划class Solution { public String longestPalindrome(String s) { //子问题:dp[i][j] 表示 s[i..j] 是否是回文子串 //动态方程:dp[i][j] s[i]s[j] (j-i2 || dp[i1][j-1]true) //范围i从大到小,因为计算dp[i][j]需要dp[i1][j-1] int n s.length(); boolean[][] dp new boolean[n][n]; int start 0; int maxLen 1; for(int in-1;i0;i--){ for(int ji;jn;j){ if(s.charAt(i) s.charAt(j)){ if(j-i2 || dp[i1][j-1]){ dp[i][j] true; int len j-i1; if(lenmaxLen){ maxLen len; start i; } } } } } return s.substring(start,startmaxLen); } }时间复杂度O(N²)空间复杂度O(N²)中心拓展法class Solution { public String longestPalindrome(String s) { int n s.length(); int maxLen 1; int start 0; for(int i 0;in;i){ //奇数向外扩展 int len1 expand(s,i,i); //偶数向外扩展 int len2 expand(s,i,i1); int len Math.max(len1,len2); if(len maxLen){ maxLen len; //计算起点 start i-(len-1)/2; } } return s.substring(start,startmaxLen); } private int expand(String s,int l,int r){ int n s.length(); while(l0 rn-1 s.charAt(l)s.charAt(r)){ l--; r; } return r-l-1; } }时间复杂度O(N²)空间复杂度O(1)