给定一个字符串 s
,找到 s
中最长的回文子串。
一、暴力解法
最暴力的解法是判断s的每个子串是否为回文串,复杂度为立方级,在此不做实现。
这里实现的是中心扩散的思想,即利用回文串中心对称的性质,遍历s的每个字符,其作为回文串的中心,依次向两边扩展更新当前回文串,若超过res则更新res。
复杂度为O(n2)。
以下代码花了几分钟写的,未优化。
class Solution { public String longestPalindrome(String s) { int len = s.length(); String res = ""; if(len==0) return res; int resLen = 0;
// 奇回文子串 for(int i=0; i<len; i++){ int cur = 1; int left = i-1; int right = i+1; while(left>=0&&right<=len-1&&s.charAt(left)==s.charAt(right)){ left--; right++; cur += 2; } if(cur>resLen){ resLen = cur; res = s.substring(++left,right); } }
// 偶回文子串 for(double i=0.5; i<=len-1.5; i++){ int cur = 0; int left = (int) (i-0.5); int right = (int) (i+0.5); while(left>=0&&right<=len-1&&s.charAt(left)==s.charAt(right)){ left--; right++; cur += 2; } if(cur>resLen){ resLen = cur; res = s.substring(++left,right); } } return res; } }
二、动态规划
dp[i][j] 表示 s[i,j](两边闭)是否为回文串。 状态转移方程: dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]。
初始化二维数组对角线为true,并只需维护该对角线以上部分,注意临界范围为 j-i<3 。若该区间为true且长度大于res,则更新目标值。
class Solution { public String longestPalindrome(String s) { int len = s.length(); if(len < 2) return s; int resLen = 1; int begin = 0; boolean[][] dp = new boolean[len][len]; for(int i=0; i<len; i++) dp[i][i] = true; for(int j=1; j<len; j++){ for(int i=0; i<j; i++){ if(s.charAt(i)!=s.charAt(j)){ dp[i][j] = false; } else { if(j - i < 3) dp[i][j] = true; else dp[i][j] = dp[i+1][j-1]; } if(dp[i][j] && j - i + 1 > resLen){ resLen = j - i + 1; begin = i; } } } return s.substring(begin,begin + resLen); } }
三、