题目描述

解题思路

双指针

和647双指针的方法一致，都是根据0和1进行扩散来判断。最终返回最长的子串，和516有区别，516是子序列。

// 从中间向左右扩散的双指针解法
public String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        String s1 = palindrome(s, i, i);
        String s2 = palindrome(s, i, i + 1);
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}
// 判断字符串区间开始是否是回文子串
public String palindrome(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    return s.substring(l + 1, r);
}

dp

和647相差不大，就是求最大的回文子串。

/**
         * 回文子串类型题
         *
         * @param s
         * @return
         */
public String longestPalindrome(String s) {
    if (s.length() == 1) {
        return s;
    }
    boolean[][] dp = new boolean[s.length()][s.length()];
    for (int i = 0; i < s.length(); i++) {
        dp[i][0] = false;
        dp[0][i] = false;
    }
    int result = 0;
    String str = String.valueOf(s.charAt(0));
    for (int i = s.length() - 1; i >= 0; i--) {
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j - i <= 1) {
                    dp[i][j] = true;
                    if (j - i > result) {
                        result = j - i;
                        str = s.substring(i, j + 1);
                    }
                } else if (dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (j - i > result) {
                        result = j - i;
                        str = s.substring(i, j + 1);
                    }
                }
            }
        }
    }
    return str;
}