LeetCode.005.LongestPalindromicSubstring 最长回文子串

题目描述

005 Longest Palindromic Substring
https://leetcode-cn.com/problems/longest-palindromic-substring/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

---

解题过程

这道题面试被问过，不会做。
这次先自己绞尽脑汁想了想，一开始想着搞个滑动窗口O(n)遍历解决，发现行不通，回文子串的子串不一定回文。
只好看了看题解，中心扩展法 很好理解，自己实现了一下，O(n^2) 复杂度，很好写。 Manacher 马拉车算法是中心扩展法的升级，将复杂度降到了O(n)，没仔细看。

中心扩展法O(n^2)

private static class SolutionV2020 {
    public String longestPalindrome(String s) {
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            // 以i为中心扩展
            String extend1 = extend(s, i, i);
            result = extend1.length() > result.length() ? extend1 : result;
            if (i + 1 < s.length()) {
                // 以 i,i+1 为中心扩展，应对长度为偶数的情况
                String extend2 = extend(s, i, i + 1);
                result = extend2.length() > result.length() ? extend2 : result;
            }
        }
        return result;
    }

    // 从 pivot1, pivot2 开始分别往左右扩展，返回最长的回文子串
    public String extend(String s, int pivot1, int pivot2) {
        while (pivot1 >= 0 && pivot2 < s.length() && s.charAt(pivot1) == s.charAt(pivot2)) {
            pivot1--;
            pivot2++;
        }
        return s.substring(pivot1+1, pivot2);
    }
}

动态规划O(n^2)

设 p[i,j] 表示子串 s[i,j] 是否回文串，若已知 s[i,j] 是否回文，则可轻松的知道左右各扩展一位的子串 s[i-1,j+1] 是否子串。
所以有递推公式：
p[i-1,j+1] = p[i,j] && s[i-1] == s[j+1] 或者写做
p[i][j] = p[i+1][j-1] && s[i] == s[j]
且有初始条件
p[i,i] = true
p[i,i+1] = s[i] == s[i+1]

填二维表的过程中，maxStr 记录当前得到的最长回文子串，每次得到一个 true 值时，比较是否比 maxStr 长度更长，如果是则更新 maxStr，填表结束后的 maxStr 就是最终结果。

观察我们要填的二维表格，由于 j > i，所以只需要用到 对角线右上方的半块表格，左下方的不需要。

  0 1 2 3 4
0 T
1   T
2     T
3       T
4         T

此外，由于 p[i][j] 依赖于 p[i+1][j-1] 的结果，也就是二维表格中 (i,j) 左下角 (i+1,j-1) 位置的值，所以我们要从左往右一列一列的竖着填表，才不会出现在计算 p[i][j] 的值时他依赖的中间结果还没计算的情况。

Manacher马拉车算法O(n)

暴力枚举所有子串O(n^3)

---

GitHub代码

algorithms/leetcode/leetcode/_005_LongestPalindromicSubstring/
https://github.com/masikkk/algorithms/tree/master/leetcode/leetcode/_005_LongestPalindromicSubstring

---