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

5. 最长回文子串

动态规划：

class Solution { public String longestPalindrome(String s) { //子问题:dp[i][j] 表示 s[i..j] 是否是回文子串 //动态方程:dp[i][j] = s[i]==s[j] && (j-i<=2 || dp[i+1][j-1]==true) //范围i从大到小,因为计算dp[i][j]需要dp[i+1][j-1] int n = s.length(); boolean[][] dp = new boolean[n][n]; int start = 0; int maxLen = 1; for(int i=n-1;i>=0;i--){ for(int j=i;j<n;j++){ if(s.charAt(i) == s.charAt(j)){ if(j-i<=2 || dp[i+1][j-1]){ dp[i][j] = true; int len = j-i+1; if(len>maxLen){ maxLen = len; start = i; } } } } } return s.substring(start,start+maxLen); } }

时间复杂度：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;i<n;i++){ //奇数向外扩展 int len1 = expand(s,i,i); //偶数向外扩展 int len2 = expand(s,i,i+1); int len = Math.max(len1,len2); if(len > maxLen){ maxLen = len; //计算起点 start = i-(len-1)/2; } } return s.substring(start,start+maxLen); } private int expand(String s,int l,int r){ int n = s.length(); while(l>=0 && r<=n-1 && s.charAt(l)==s.charAt(r)){ l--; r++; } return r-l-1; } }

时间复杂度：O(N²)

空间复杂度：O(1)