找出一个字符串的最长回文子字符串
字符串最长为1000,比较短，我们可以采用动态规划的思想。 dp[i][j]表示从下标为i到下标为j的字符串是否为回文串 dp[i][j]=true if s[i]=s[j]且dp[i+1][j-1]=true
public String longestPalindrome(String s) { int n=s.length(); boolean dp[][]=new boolean[n][n]; int max=0,index=0; for(int i=0;i<n;i++){ dp[i][i]=true; if(i>0&&s.charAt(i)==s.charAt(i-1)){ dp[i-1][i]=true; max=2; index=i-1; } } //长度为i的回文子串 for(int i=3;i<=n;i++) for(int j=0;j<n+1-i;j++){ if(s.charAt(j)==s.charAt(j+i-1)&&dp[j+1][j+i-2]){ dp[j][j+i-1]=true; max=i; index=j; } } return s.substring(index, index+max); }新闻热点
疑难解答
