leetcode - 00005 最长回字串

[meishaoming]

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

我第一眼想到的方法是：

从头开始往后取字符，对于第 i 个字符
  看看它后边的字符是否相同，
      如果相同的话，offset + 1，continue 继续取 i 下一个字符
  看看 s[i-1] == s[i+offset+1]，
      如果不等的话，continue 取 i 下一个字符
      如果相等，则比较 s[i-2] == s[i+offset+2]
         ...
      比较 s[i-n] == s[i+offset+n]
        ..

但我实现不出来（这也太悲伤了😭）。

看了答案。

解法一：暴力法

穷举所有的子串，然后判断每个子串是否是回文，记下最长的那个子串。

于这个问题被分解为：

1. 如何得到字符串 s 的所有子串？
2. 如何判断一个字符串是否是回文？

对于一个字符串 s，其长度为 n，那么它可能的子串（单个字符也算）有多少个？

n = 1, 有 1 个 n = 2, 有 3 个 n = 3, 有 6 个 (abc => a, b, c, ab, bc, abc) n = 4, 有 10 个 (abcd => a, b, c, d, ab, bc, cd, abc, bcd, abcd) ... n = n, 有 n(n+1)/2 个 (n + (n-1) + (n-2) + ... + 1 个，即 (n+1) * (n/2))

打印出字符串 s 的所有子串：

def all_sub_string(s):
    for i in range(len(s)):
        j = i+1
        while j <= len(s):
            print(s[i:j])
            j += 1

判断一个字符串是否是回文：

def is_palindrome(s):
    for i in range(len(s) // 2):
        if s[i] != s[-(1+i)]:
            return False
    return True

把上边两个拼起来，就是暴力解法了：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def is_palindrome(s):
            for i in range(len(s) // 2):
                if s[i] != s[-(1+i)]:
                    return False
            return True

        longest_sub_str = ""
        for i in range(len(s)):
            j = i+1
            while j <= len(s):
                sub_str = s[i:j]
                if is_palindrome(sub_str):
                    if len(sub_str) > len(longest_sub_str):
                        longest_sub_str = sub_str
                j += 1
        return longest_sub_str

总的子串有 n(n+1)/2 个，判断一个字符串是否是回文的时间复杂度为 O(n)，所以整个解法的时间复杂度为 O(n^3 )。

提交的结果也一点不让我意外。

这个执行超时用例是一个长度 999 字节的 "abababab......aba"，整个字符串就是一个回文。在我的电脑上计算都花了 5.41 秒。

这个暴力法也有可以优化的地方。比如已经找到一个长度为 5 的回文，接下来的子串长度如果没有长于 5 就不用计算、直接跳过就好了。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def is_palindrome(s):
            for i in range(len(s) // 2):
                if s[i] != s[-(1+i)]:
                    return False
            return True

        longest_sub_str = ""
        for i in range(len(s)):
            j = i+1
            while j <= len(s):
                if (j - i) > len(longest_sub_str):
                    sub_str = s[i:j]
                    if is_palindrome(sub_str):
                        if len(sub_str) > len(longest_sub_str):
                            longest_sub_str = sub_str
                j += 1
        return longest_sub_str

优化后在电脑上运行快了很多，现在只要 0.2s 左右。但提交还是「超出时间限制」。

解法二：

答案里起的名字叫动态规划。

动态规划（英语：Dynamic programming，简称DP）是什么意思呢？ 还是去看维基百科吧 https://zh.wikipedia.org/wiki/动态规划

用在我们这里的问题，对于 "ababa"，按上面的算法我们判断它是不是一个回文，要从最中间的 a 算起，至少再比较两次（b==b, a==a) 才能确定它是一个回文。

而如果我们事先已经知道 "bab" 是一个回文，那么我们只需比较一次（a==a）就能确定了。这样就可以减少比较次数。

所以现在算法改为：

1. 先用一个映射表，里边存储一个子串是不是回文
2. 把字符串 s 分解出所有子串
3. 对每一个子串的判断就是两步： a. 它的最左和最右是否相等？如果不等就不是回文 b. 它里边的一层（去除最左最右）是不是已经在映射表里了？如果是就直接拿结果，如果不是就算一次存到映射表里

这个解法的好处是减少了运算次数，减少了多少次呢？以前算一个字符串是不是回文时间复杂度为O(n)，现在是如果这个字符串已经算过，就直接取结果，如果没算过，才需要再去计算。

缺点是用一个巨大的映射表，有多大呢？最坏的情况是子串的个数，即 n(n+1)/2。所以空间复杂度为 O(n^2)。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def is_palindrome(s):
            for i in range(len(s) // 2):
                if s[i] != s[-(1+i)]:
                    return False
            return True

        stored_map = {}
        longest_sub_str = ""
        for i in range(len(s)):
            j = i+1
            while j <= len(s):
                sub_str = s[i:j]
                j += 1
                if len(sub_str) <= 2:
                    if sub_str[0] != sub_str[-1]:
                        continue
                else:
                    if sub_str[0] != sub_str[-1]:
                        continue
                    else:
                        sub_sub_str = sub_str[1:-1]
                        if sub_sub_str not in stored_map:
                            stored_map[sub_sub_str] = is_palindrome(sub_sub_str)
                        if stored_map[sub_sub_str] != True:
                                continue
                if len(sub_str) > len(longest_sub_str):
                    longest_sub_str = sub_str
        return longest_sub_str

在电脑上跑刚才失败的用例（999 个 "ababab....aba"），用的时间只需要 0.563 秒，短了 10 倍

但是提交还是失败，失败在 1000 个 "1" 或 "c" 这样的用例上

解法三：

上边的方法还是犯了一个错误。还是计算了所有的子串。实际上不需要，只需要在已经确定的回文两边继续找就行了。所以方法改进为：

1. 所有单字符肯定是回文了
2. 找所有双字符的回文，比如 "aa", "bb" 这样的
3. 找所有三字符的回文，比如 "aaa", "bab" 这样的,
4. 在所有双字符回文的两边扩散，找四字回文，"abba"，"aaaa"
5. 在所有三字符两边扩散，找五字回文 "cbabc"

这是由短往长找。换一种找法：

1. 确定一个单字（单字肯定是回文）
2. 看它两边是否有双字回文，比如 "aa"
3. 如果是的话，再穷尽所有连续的相同字符，比如 "aaaaaa"
4. 再在它两边扩散着找
5. 下一次找就要跳过这些连续的字符，比如 "aaaaaab" ，下一次从 b 开始找，跳到步骤2

这种找法就跟我一开始想的那个解法差不多了，可是还是不知道怎么实现。

解法四：

看答案才明白的。从中心向两边找，比如：

1. 以单个字符为起点，"a" 就向它两边连续找，这样可以找到"bab", "cbabc", "aaa" 这样的情况，总共要找 n 次（因为字符串 s 有 n 个字符）
2. 以两个字符中间为起点，因为存在 "aa", "baab" 这样的情况，所以要从它们的中间找，总共要找 n-1 次

所以加起来总共找了 2n-1 次，每次算回文的复杂度是 O(n)，所以最后的时间复杂度为 O(n^2)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand_around_center(s, left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left -1

        start = end = 0
        for i in range(len(s)):
            len1 = expand_around_center(s, i, i)
            len2 = expand_around_center(s, i, i+1)
            l = max(len1, len2)
            if l > (end - start):
                start = i - (l-1)//2
                end = i + l//2
        return s[start:end+1]

总算是过了

上边的写法比较 C 一点，看了一下别人的解答，感觉用 Python 的习惯应该这样写（尽量不用数组下标？）：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand_around_center(s, left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]

        if not s:
            return s
        res = s[0]
        for i in range(len(s)):
            s1 = expand_around_center(s, i, i)
            s2 = expand_around_center(s, i, i+1)
            res = max(res, s1, s2, key=len)
        return res

解法五

到这里我终于知道之前的想法该如何实现了：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand_around_center(s, left, right):
            same_num = 1
            while (right+same_num) < len(s) and s[left] == s[right+same_num]:
                same_num += 1
            same_num -= 1
            right += same_num
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1: right], same_num

        if not s: return s
        res = s[0]
        i = 0
        while i < len(s): 
            sub_s, num = expand_around_center(s, i, i)
            if len(sub_s) > len(res):
                res = sub_s
            i += num + 1
        return res

提交结果猛猛猛。快在跳过了相同的字符，比如 "1111111" 直接一次 expand 就出结果了。

解法六 马拉车

...