5. Longest Palindromic Substring

• 求最长回文子串（连续）

• 最优解法是Manacher算法

• - LeetCode

• 这个题要和最长回文子序列（不连续）对比着看516. Longest Palindromic Subsequence

思路

如果和最长回文子序列采用同样思路

• 首先需要找出字符串中的最长回文子串，也就是返回字符串从0 - n (字符串长度)之间的最长回文子串

• 情况一： 如果当前字符串的头尾字符相等，那么有可能整体都是回文字符。在进入判别条件

• 子情况一： 头尾各缩进一位的子字符串如果是回文串，那么整体的s就是最长的回文子串。

• 子情况二： 头尾各缩进一位的字符串如果不是回文串，那么整体的s肯定不是回文串。

• 情况二： 如果当前的字符串头尾字符不相等 ，那么当前的字符串肯定不是回文字符。所以当前字符串的最大回文子串可能出自两个地方。

• 左边缩进一个字符后的字符串的最大回文字符串。

• 右边缩进一个字符后的字符串的最大回文字符串。

对应代码

class Solution {
    private String[][] memo = new String[1001][1001];
    private int[] longest = new int[2];
    private String lps(int i, int j, String s){
        String tmp = "";
        if(memo[i][j] != null){
            return memo[i][j];
        }
        if(i == j){
            return s.substring(i, j + 1);
        }
        if(i > j){
            return "";
        }
       // 分析出来的情况一（如果两头都缩进后的最大回文子串长度不等于缩进后字符串，那么子字符串肯定也不是回文字符串）
        if(s.charAt(i) == s.charAt(j) && lps(i+1, j-1, s).length() == j - i - 1){
            tmp = s.substring(i ,j+1);
        }else{
            // 分析对应的情况二
            tmp = "";
            String s1 = lps(i + 1, j, s);
            String s2 = lps(i, j - 1, s);
            if(s1.length() > s2.length()){
                tmp = s1;
            }else{
                tmp = s2;
            }
        }
        // System.out.println(tmp);
        memo[i][j] = tmp;
        return tmp;
    }

    public String longestPalindrome(String s) {
        return lps(0, s.length() - 1, s);
    }
}