5. Longest Palindromic Substring (M)

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

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Solution:

https://labuladong.gitee.io/algo/4/32/139/ Version 1: Two pointers

对于这个问题，我们首先应该思考的是，给一个字符串 s，如何在 s 中找到一个回文子串？

有一个很有趣的思路：既然回文串是一个正着反着读都一样的字符串，那么如果我们把 s 反转，称为 s'，然后在 s 和 s' 中寻找最长公共子串，这样应该就能找到最长回文子串。

比如说字符串 abacd，反过来是 dcaba，它的最长公共子串是 aba，也就是最长回文子串。

但是这个思路是错误的，比如说字符串 aacxycaa，反转之后是 aacyxcaa，最长公共子串是 aac，但是最长回文子串应该是 aa。

虽然这个思路不正确，但是这种把问题转化为其他形式的思考方式是非常值得提倡的。

下面，就来说一下正确的思路，如何使用双指针。

寻找回文串的问题核心思想是：从中间开始向两边扩散来判断回文串。对于最长回文子串，就是这个意思：

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

但是呢，我们刚才也说了，回文串的长度可能是奇数也可能是偶数，如果是 abba这种情况，没有一个中心字符，上面的算法就没辙了。所以我们可以修改一下：

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

PS：读者可能发现这里的索引会越界，等会会处理。

二、代码实现

按照上面的思路，先要实现一个函数来寻找最长回文串，这个函数是有点技巧的：

String palindrome(String s, int l, int r) {
    // 防止索引越界
    while (l >= 0 && r < s.length()
            && s.charAt(l) == s.charAt(r)) {
        // 向两边展开
        l--; r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substring(l + 1, r);
    }

为什么要传入两个指针 l 和 r 呢？因为这样实现可以同时处理回文串长度为奇数和偶数的情况：

for 0 <= i < len(s):
    # 找到以 s[i] 为中心的回文串
    palindrome(s, i, i)
    # 找到以 s[i] 和 s[i+1] 为中心的回文串
    palindrome(s, i, i + 1)
    更新答案

下面看下 longestPalindrome 的完整代码：

public String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        // 以 s[i] 为中心的最长回文子串
        String s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        String s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}

至此，这道最长回文子串的问题就解决了，时间复杂度 O(N^2)，空间复杂度 O(1)。

值得一提的是，这个问题可以用动态规划方法解决，时间复杂度一样，但是空间复杂度至少要 O(N^2) 来存储 DP table。这道题是少有的动态规划非最优解法的问题。

另外，这个问题还有一个巧妙的解法，时间复杂度只需要 O(N)，不过该解法比较复杂，我个人认为没必要掌握。该算法的名字叫 Manacher’s Algorithm（马拉车算法），有兴趣的读者可以自行搜索一下。

Version 2: DP

/class Solution {
    public String longestPalindrome(String s) {
        // 处理异常情况 
        if(s==null||s.length()<=1) return s; 
        // dp[i][j] 表示从i到j的字符串中的最长子串
        // dp[i][i] 表示单个字符肯定是回文子串
        boolean[][] dp = new boolean[s.length()][s.length()];
        String result= null;
        int length = -1;
        for(int i = s.length()-1;i>=0;i--){
            for(int j = i;j<s.length();j++ ){
                if(i==j) dp[i][j] = true;
                else if(j-i==1&&s.charAt(i)==s.charAt(j)) dp[i][j] = true;
                else if(s.charAt(i)==s.charAt(j)) dp[i][j] = dp[i+1][j-1];
                else dp[i][j] = false;
                if(dp[i][j]&&j-i>length){
                    length = j-i;
                    result = s.substring(i,j+1);
                }
            }
            
        }
        return result;
    }
}
贴一个动态规划的解法

Previous125. Valid Palindrome(E)Next42. Trapping Rain Water

Last updated 2 years ago