找出一個字符串的最長回文子字符串
字符串最長為1000,比較短，我們可以采用動態(tài)規(guī)劃的思想。 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); }新聞熱點
疑難解答
