题目地址

https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：
输入: "cbbd" 输出: "bb"

题解

暴力枚举

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        int resultBegin = 0;
        int maxLength = 0;
        for (int begin = 0; begin < length; ++ begin) {
            for (int end = length - 1; end >= begin; -- end) {
                if (isPalindrome(s, begin, end)) {

                    // 保存最长的回文子串
                    int newLength = end - begin + 1;
                    if (newLength > maxLength) {
                        maxLength = newLength;
                        resultBegin = begin;
                    }
                    break;
                }
            }
        }

        return s.substring(resultBegin, resultBegin + maxLength);
    }

    public boolean isPalindrome(String s, int begin, int end) {
        int length = (end - begin + 1) / 2;
        for (int i = 0; i < length; ++ i) {
            if (s.charAt(begin + i) != s.charAt(end - i)) {
                return false;
            }
        }

        return true;
    }
}

时间复杂度 O(n^3)，n 为字符串长度。

上面枚举子串 [begin, end] 的操作是必需的。

可以看看怎么优化 isPalindrome() 的逻辑，可以在常量时间判断子串 [begin, end] 是否是一个回文串。

动态规划

解题之前先来思考一个问题：如何判断一个子串 [begin, end] 是否是一个回文串？

// case 1
// end == begin，只有一个字符的情况下
// [begin, end] 是回文串

// case 2
// end = begin + 1，只有两个字符的情况下，两个字符相同
// 即 s.charAt(begin) == s.charAt(end)
// [begin, end] 是回文串

// case 3
// [begin+1, end-1] 是回文串的情况下，s.charAt(begin) == s.charAt(end)
// 如 aba 是回文串，xabax 也是回文串
// [begin, end] 是回文串

我们用 dp[begin][end] 表示 [begin, end] 子串是否是回文串，为 true 表示是回文串，为 false 表示不是回文串

把上面的三个 case 用代码描述为：

boolean dp[][] = new boolean[length][length];

// 因为要从 begin+1 推导 begin 的值，所以要从大到小遍历
for (int begin = length - 1; begin >= 0; --begin) {
    // 因为要从 end-1 推导 end 的值，所以要从小到大遍历
    for (int end = begin; end < length; ++end) {
        // case 1
        if (end == begin) {
            dp[begin][end] = true;
        }

        // case 2
        if (end == begin + 1 && s.charAt(begin) == s.charAt(end)) {
            dp[begin][end] = true;
        }

        // case 3
        if (dp[begin+1][end-1] && s.charAt(begin) == s.charAt(end)) {
            dp[begin][end] = true;
        }
    }
}

构建上述 dp 数组的时间复杂度为 O(n^2)，n 为字符串长度。

通过 dp 数组，我们可以在 O(1) 的时间复杂度中判断 [begin, end] 子串是否是回文串。

我们还可以在构建 dp 数组的同时得到最长的回文子串，完整的代码如下所示：

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        int resultBegin = 0;
        int maxLength = 0;

        boolean dp[][] = new boolean[length][length];
        // 因为要从 begin+1 推导 begin 的值，所以要从大到小遍历
        for (int begin = length - 1; begin >= 0; --begin) {
            // 因为要从 end-1 推导 end 的值，所以要从小到大遍历
            for (int end = begin; end < length; ++end) {
                // case 1
                if (end == begin) {
                    dp[begin][end] = true;
                }

                // case 2
                if (end == begin + 1 && s.charAt(begin) == s.charAt(end)) {
                    dp[begin][end] = true;
                }

                // case 3
                // 需要判断数组索引下标是否在可以访问的范围内
                boolean inBounds = begin+1 < length && end-1 > 0;
                if (inBounds && dp[begin+1][end-1] && s.charAt(begin) == s.charAt(end)) {
                    dp[begin][end] = true;
                }

                // 保存最长的回文子串
                if (dp[begin][end]) {
                    int newLength = end - begin + 1;
                    if (newLength > maxLength) {
                        maxLength = newLength;
                        resultBegin = begin;
                    }
                }
            }
        }

        return s.substring(resultBegin, resultBegin + maxLength);
    }
}

时间复杂度为：O(n^2)，n 为字符串的长度。
空间复杂度为：O(n^2)，n 为字符串的长度。

上述优化思路和 面试题 17.23. 最大黑方阵 的优化思路是一样的。
通过预处理，我们缩减其中某一个步骤的时间复杂度，从而使整体的时间复杂度下降一个 O(N)。