如何寻找最长回文子串 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何寻找最长回文子串

[NobiGo]

class Solution {
    public String longestPalindrome(String s) {
        // 处理异常情况 
        if(s==null||s.length()<=1) return s; 
        // dp[i][j] 表示从i到j的字符串中的最长子串
        // dp[i][i] 表示单个字符肯定是回文子串
        boolean[][] dp = new boolean[s.length()][s.length()];
        String result= null;
        int length = -1;
        for(int i = s.length()-1;i>=0;i--){
            for(int j = i;j<s.length();j++ ){
                if(i==j) dp[i][j] = true;
                else if(j-i==1&&s.charAt(i)==s.charAt(j)) dp[i][j] = true;
                else if(s.charAt(i)==s.charAt(j)) dp[i][j] = dp[i+1][j-1];
                else dp[i][j] = false;
                if(dp[i][j]&&j-i>length){
                    length = j-i;
                    result = s.substring(i,j+1);
                }
            }
            
        }
        return result;
    }
}

贴一个动态规划的解法