Leetcode 5 Longest Palindrome Substring

发表于 |

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

示例 1：
输入: “babad”
输出: “bab”
注意: “aba”也是一个有效答案。

示例 2：
输入: “cbbd”
输出: “bb”

题意分析：
经典题型，找字符串中最长的回文子串(substring)，子串的定义是要求必须连续的，和子序列（subsequence）是两个不同的东西！

思路分析：
在我的多篇博客里始终强调，我们解题一定要看数据范围，leetcode上很多题并不会给出数据范围，这其实特别不好，数据的大小完全决定了我们是否可以采取高复杂度的方法。

这道题s长度不超过1000，显然是在暗示我们O(n^2)的方法是可行的。

一句题外话：通常这类最长子串，最长子序列问题都是可以用dp来求解的，并且他们的dp定义大多类似，一般为dp[i][j]代表在s[i:j+1]中的所求结果，显然dp[0][n]即为最后所求。

这道题也是一样，我们定义dp[i][j]代表s[i:j+1]中最长回文子串的长度，那么dp[0][n]即为所求！

递推式分析：
那么dp[i][j]如何变化呢，因为子串要求连续，如果s[i] != s[j]，显然dp[i][j] = 0；
如果s[i] == s[j]，我们需要知道中间部分是否也是回文子串，若是，dp[i][j] = 2 + dp[i+1][j-1]，若不是，则dp[i][j] = 0

初始状态分析：
显然dp[i][i] = 1
由于dp[i][j] = 2 + dp[i+1][j-1]需要满足j-1 >= i+1, 即j-i >= 2,所以j == i+1这种情况要单独处理！

注意这道题实际要求的并不是长度，而是字符串，所以我们使用dp来记录长度，用另一个变量cnt，来记录下标i,j，最后返回s[i:j+1]即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 2964ms, beats 26.39%
class Solution(object):
    def longestPalindrome(self, s):
        n = len(s)
        dp = [[1]*n for _ in range(n)]
        cnt,start,end = 0,0,0
        for i in range(n-1,-1,-1):
            for j in range(i+1,n):
                if s[i] != s[j]: dp[i][j] = 0; continue
                if j == i+1:# 单独处理 j == i+1
                    dp[i][j] = 2
                else:
                    # 判断中间子串是否也是回文串
                    if dp[i+1][j-1] > 0:
                        dp[i][j] = dp[i+1][j-1] + 2
                    else:
                        dp[i][j] = 0
                # 记录结果
                if dp[i][j] > cnt:
                    cnt = dp[i][j]
                    start,end = i,j
        return s[start:end+1]

你可能会好奇为什么这个算法只beats这么点人。那是因为单从这道题的数据来说，还有着更优的解法。

也就是依次遍历s中的每一个字符ss，以ss作为回文串的中点向两边扩展，然后记录长度！
但是我个人更偏向于第一种解法(dp)，因为这才是这类型题的标准解法，不过实际我第一次做的时候也是采用的这种遍历的方法。这里给出代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def longestPalindrome(self, s):
        def getPalinLength(s,i,j):
            while i >= 0 and j < len(s) and s[i] == s[j]:
                i -= 1
                j += 1
            return (i+1, j-i-1)
        
        start,cnt = 0,0
        for i in range(len(s)):
            s1, l = getPalinLength(s,i,i)
            if l > cnt:
                cnt = l
                start = s1
            s2, l = getPalinLength(s,i,i+1)
            if l > cnt:
                cnt = l
                start = s2
        return s[start:start+cnt]

其实还有更优的解法，但是太累了，不想写了！