LeetCode（5）：最长回文子串

淩亂°似流年 2021-11-06 00:44 352阅读 0赞

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

![20190809152320317.png][]

### 解法 1: 暴力破解 ###

暴力求解，列举所有的子串，判断是否为回文串，保存最长的回文串

public boolean isPalindromic(String s) {
            int len = s.length();
            for (int i = 0; i < len / 2; i++) {
                if (s.charAt(i) != s.charAt(len - i - 1)) {
                    return false;
                }
            }
            return true;
        }
    
    // 暴力解法
    public String longestPalindrome(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++)
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        return ans;
    }

时间复杂度：两层 for 循环 O(n²），for 循环里边判断是否为回文 O(n），所以时间复杂度为 O(n³）。

空间复杂度：O(1），常数个变量。

### 解法2：最长公共子串 ###

常见错误

有些人会忍不住提出一个快速的解决方案，不幸的是，这个解决方案有缺陷(但是可以很容易地纠正)：

反转 S，使之变成 S ′。找到 S 和 S ′之间最长的公共子串，这也必然是最长的回文子串。这似乎是可行的，让我们看看下面的一些例子。例如，S = “caba”, S' =“abac”   S 以及 S'之间的最长公共子串为“aba”，恰恰是答案。让我们尝试一下这个例子：S =“abacdfgdcaba”, S' = “abacdgfdcaba”   S 以及 S ′之间的最长公共子串为“abacd”。显然，这不是回文。

算法

我们可以看到，当 S 的其他部分中存在非回文子串的反向副本时，最长公共子串法就会失败。为了纠正这一点，每当我们找到最长的公共子串的候选项时，都需要检查子串的索引是否与反向子串的原始索引相同。如果相同，那么我们尝试更新目前为止找到的最长回文子串；如果不是，我们就跳过这个候选项并继续寻找下一个候选。

这给我们提供了一个复杂度为 O(n^2)   动态规划解法，它将占用 O(n^2)的空间（可以改进为使用 O(n) 的空间）

### 解法 3: 扩展中心 ###

我们知道回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。

由于存在奇数的字符串和偶数的字符串，所以我们需要从一个字符开始扩展，或者从两个字符之间开始扩展，所以总共有 n+n-1 个中心。

public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

时间复杂度：O(n²）。

空间复杂度：O(1）。

[20190809152320317.png]: /images/20211104/0a4e7f9562f34b358a3dcda76cb0572c.png