最长回文子串

题目链接：leetcode 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 仅由数字和英文字母（大写和/或小写）组成

题解

法一：暴力解

不过多赘述，这里注意区分一下两个概念：

• 字串（substring）：原始字符串的一个连续子集
• 子序列（subsequence）：原始字符串的一个子集

即：一个要求连续，一个不要求

class Solution {
    public String longestPalindrome(String s) {
        if (s == null)
            return null;
        int len = s.length();
        if (len < 2)
            return s;

        char[] chars = s.toCharArray();
        //记录起始位置和长度，便于进行substring处理
        int start = 0, max_len = 1;	//最长回文串长度的初始值为1，表示如果找不到就返回1个字符
        
        //枚举所有长度严格大于 1 的子串，charArray[i...j]
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > max_len && is_str(chars, i, j)) {
                    start = i;
                    max_len = j - i + 1;
                }
            }
        }
        return s.substring(start, start + max_len);
    }

    //判断字串s[left...right] 是不是回文串
    boolean is_str(char[] chars, int begin, int end) {
        while (begin < end) {
            if (chars[begin] != chars[end])
                return false;
            begin++;
            end--;
        }
        return true;
    }
}

复杂度分析：

时间复杂度：$O(n^3)$，这里 n 为字符串的长度

空间复杂度：$O(1)$，只用到常数个临时变量

（提交上去还是能通过的。。。）

法二：中心扩散法

法一的思路相当于是从两边往中间去判断是不是回文串，换个思路，我们可以枚举所有可能的回文串的中心位置，向两边逐渐扩展去判断是不是回文串。

当然，回文串的中心可能是一个字符，也可能是相邻的两个字符，需要分奇偶来讨论：

代码：

class Solution {
    public String longestPalindrome(String s) {
        if (s == null)
            return null;
        int len = s.length();
        if (len < 2)
            return s;

        char[] chars = s.toCharArray();
        int start = 0, max_len = 1;
        for (int i = 0; i < len - 1; i++) {
            int oddLen = expandAroundCenter(chars, i, i);	//奇数
            int evenLen = expandAroundCenter(chars, i, i + 1);	//偶数

            int curMaxLen = Math.max(oddLen, evenLen);
            if (curMaxLen > max_len) {
                max_len = curMaxLen;
                start = i - (max_len - 1) / 2;  //总结奇数和偶数一起满足的规律，建议画图分奇偶自己试一下
            }
        }
        return s.substring(start, start + max_len);
    }

    //begin和end都可以取到
    int expandAroundCenter(char[] chars, int begin, int end) {
        // 当 left = right 时，回文中心是一个字符，回文串的长度是奇数
        // 当 left = right + 1 时，回文中心是两个字符，回文串的长度是偶数
        int len = chars.length;
        int i = begin, j = end;
        while (i >= 0 && j < len) {
            if (chars[i] == chars[j]) {
                i--;
                j++;
            } else {
                break;
            }
        }
        //注意循环跳出之后，chars[i] != chars[j]
        //回文串的长度是 j - i + 1 - 2 = j - i - 1
        return j - i - 1;
    }
}

复杂度分析：

时间复杂度：$O(n^2)$，枚举中心位置的个数是 $2(n-1)$，每一次向两边扩散检测是否是回文

空间复杂度：$O(1)$，只用到常数个临时变量

（时间复杂度降低了一个数量级，交上去相比法一有质的提升）

法三：动态规划

回文串是天然满足状态转移性质的，这是因为：

一个回文去掉两头之后，剩下的部分依然是回文

这里回文串的长度大于 2。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。

根据这样的思路，我们就可以用动态规划的方法解决本题。我们用 $P(i,j)$ 表示字符串 $s$ 的第 $i$ 到 $j$ 个字母组成的串（下文表示成 $s[i:j]$）是否为回文串：

$$
P(i,j)=
\left{
\begin{aligned}
true \qquad&如果子串 S_i…S_j 是回文串\
false \qquad&其他情况\
\end{aligned}
\right.
$$