13-最长回文子串

最长回文子串

该算法的基本思路是，从字符串的第一个字符开始遍历，以每个字符为中心分别向左右两边展开，并比较左右两边的字符是否相等。如果相等，则继续展开；否则，回文子串查找结束。

在查找过程中，不仅要记录最长回文子串的起始和结束位置，还要记录最长回文子串本身。当找到新的最长回文子串时，更新最长回文子串的值即可。这样做可以保证返回的结果一定是字符串中的最长回文子串。

public class LongestPalindromicSubstring {
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String longestPalindrome = s.substring(0, 1);

        // 边界情况：每个长度为 1 的子串都是回文子串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 遍历每个长度大于 1 的子串
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (len == 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (len > longestPalindrome.length()) {
                            longestPalindrome = s.substring(i, j + 1);
                        }
                    }
                }
            }
        }

        return longestPalindrome;
    }
}

采用动态规划算法来查找最长回文子串。具体而言，我们使用一个二维布尔型数组 dp 来表示字符串中每个子串是否为回文子串。其中，dp[i][j] 表示从第 i 个字符到第 j 个字符组成的子串是否为回文子串。

首先，我们给 dp 数组的对角线（即 dp[i][i]）赋值为 true，以保证每个长度为 1 的子串都是回文子串。然后，我们遍历所有长度大于 1 的子串，并根据以下两种情况来更新 dp 数组：

• 如果子串的首末字符不相等，则它一定不是回文子串；
• 如果子串的首末字符相等，则需要进一步检查它去掉首尾字符后剩余部分是否为回文子串。如果是，则当前子串也是回文子串；否则，它不是回文子串。

在检查子串是否为回文子串的同时，我们还要记录下最长回文子串本身。如果新找到的回文子串长度比已知的最长回文子串更长，则更新最长回文子串的值。

验证：

public class Test {
    public static void main(String[] args) {
        String s = "babad";
        String expected = "bab";
        String actual = LongestPalindromicSubstring.longestPalindrome(s);
        System.out.println("actual.equals(expected) = " + actual.equals(expected));//true

        s = "cbbd";
        expected = "bb";
        actual = LongestPalindromicSubstring.longestPalindrome(s);
        System.out.println("actual.equals(expected) = " + actual.equals(expected));//true
    }
}