题目描述

给定一个字符串，求字符串的最长回文子串

解法

1. 中心扩散法
2. 动态规划法

中心扩散法
从一个点出发，比较周围的字符能否加入到回文串中，如果可以，更新回文串长度

    public static String reseveString(String str){

        int start = 0;//最长回文串开始的标志
        int maxLen = 0;//最长回文串的长度

        //考虑aba的部分
        for(int i = 1; i < str.length()-1;i++){
            int left = i-1;
            int right = i+1;
            while(left >= 0 && right <str.length()&&str.charAt(left)==str.charAt(right)){
                if(maxLen < right - left + 1){
                    start = left;
                    maxLen = right - left + 1;
                }
                left--;
                right++;
            }

        }


        // 考虑abba情况
        for(int i = 0; i < str.length()-1;i++){
            int left = i;
            int right = i + 1;
            while(left >= 0 && right < str.length()&& str.charAt(left)==str.charAt(right)){
                if(maxLen < right - left + 1){
                    start = left;
                    maxLen = right - left + 1;
                }
                left--;
                right++;
            }
        }

        return str.substring(start,start+maxLen);
    }

动态规划
dp[i][j] = dp[i-1][j+1]+2
当前回文串基于子串

    public static String reserveDp(String str){
        int start = 0;
        int end = 0;
        int maxLen = 0;

        boolean dp[][] = new boolean[str.length()][str.length()];

        for(int j = 0; j < str.length();j++){
            for(int i = 0; i < j;i++){
                if(str.charAt(i)==str.charAt(j)&&(j-i<=2||dp[i+1][j-1])){
                    dp[i][j] = true;
                    if(maxLen < j - i + 1){
                        maxLen = j - i + 1;
                        start = i;
                        end = j;
                    }
                }
            }
        }

        if(start == end){
            return Character.toString(str.charAt(0));
        }

        return str.substring(start,start+maxLen);
    }