5 最长回文子串

5 最长回文子串

这道题是一道面试常考题，这里主要记录两种方法，一种是基于动态规划进行求解，另一种方法是在动态规划的基础上进行进一步的改进。

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

题解

考虑一个回文字符串他有什么特点呢？这里以一个示例进行说明，例如这个abaaba这是一个典型的回文串，分析这个回文串我们可以发现一个重要的特征 一个回文串去掉头部和尾部的字符之后依然是一个回文串 。

下面给出形式化的描述：我们用表示字符串的第 到 个字母组成的串是否为回文串，那么我们可以写出下面的状态转移方程：

另外我们考虑边界条件：对于长度为1的字符串显然是一个回文串，对于长度为2的字符串要满足回文串的条件需要构成字符串的两个字符相同。
根据这个思路，我们就可以完成动态规划了，最终的答案即为所有 中（即子串长度）的最大值。

最后这道题在编写程序的时候要注意一个细节问题：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此下面程序的状态转移的核心部分外层循环我们设置为字串的长度。
**
这种方案下的时间复杂度为, 空间复杂度为

方法一 动态规划

class Solution {
    public String longestPalindrome(String s) {
        if (s == null)
            return null;

        int len = s.length();
        boolean[][] dp = new boolean[len][len];

        // 使用left和right记录答案的边界
        int left = 0;
        int right = 0;
        for (int subLen = 0; subLen < len; subLen++) {
            for (int i = 0; subLen + i < len; i++) {
                if (subLen == 0) {
                    dp[i][i + subLen] = true;
                } else if (subLen == 1) {
                    dp[i][i + subLen] = (s.charAt(i) == s.charAt(i + subLen));
                } else {
                    dp[i][i + subLen] = (dp[i + 1][i + subLen - 1] && s.charAt(i) == s.charAt(i + subLen));
                }

                if (dp[i][i + subLen] && (right - left) < subLen + 1) {
                    left = i;
                    right = i + subLen + 1;
                }
            }
        }

        return s.substring(left, right);
    }
}

下面给出这道题的另一种空间优化的版本，这里的思路和上面的比较相似主要用到这两点：

• 对于长度为1的字符串显然是一个回文串，对于长度为2的字符串要满足回文串的条件需要构成字符串的两个字符相同;
• 一个回文串去掉头部和尾部的字符之后依然是一个回文串

这里的第二点我们也可以这样思考： 对于一个回文串如果需要它扩展之后依然是一个回文串，那么我们需要满足在这个回文字符串两端进行同时扩展，并且扩展的时候满足两端同时扩展相同的字符 (注意字符串长度和边界的限制)。

有了上面的思路之后我们就可以对所有长度为1和长度为2的回文字符串进行扩展，找到能够扩展得到的最大长度。

方法二 中心扩展法

class Solution {
    public String longestPalindrome(String s) {
        if (s == null)
            return null;

        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i ++) {
            int len1 = extendFromCentera(s, i, i);
            int len2 = extendFromCentera(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > right - left) {
                left = i - (len - 1) / 2;
                right = i + len / 2;
            }
        }

        return s.substring(left, right + 1);
    }

    private int extendFromCentera(String s, int left, int right) {
        // 返回的是从中心扩展能够得到的最长回文串的长度
        if (s == "")
            return 0;

        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }

        return right - left - 1;
    }
}

两种解法种都使用先记录边界最后返回子串是为了避免每次使用java String类中的substring()方法返回新的字符串消耗时间和空间