跳到主要内容

5. 最长回文子串[Medium]

5. 最长回文子串[Medium]​

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

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"
通过次数285,604提交次数933,229

Forth Try​

2020-10-09

没想到已经三四个月过去了，太可怕了。

其实一下子也是忘记怎么求解了，只知道这是一道非常常见的题目。

使用动态规划暴力法，如果把gap为0放在循环里，直接就超时了。把gap为0拿出来，才勉强通过。

其实这题目最合适的解法还是second try里的从中心开花，才能减少各种无意义的选择。 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not len(s):
            return ""
        cache = [[""] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            cache[i][i] = True 

        maxlen = 0
        bounary = [0, 0]
        for gap in range(1, len(s)):
            for i in range(0, len(s) - gap):
                j = i + gap 
                # if j == i:
                #     cache[i][j] = True 
                if j == i + 1:
                    cache[i][j] = s[i] == s[j]
                else:
                    cache[i][j] = cache[i+1][j-1] and s[i] == s[j]   
                    
                if cache[i][j] and (j - i + 1) > maxlen:
                    maxlen = j - i + 1
                    bounary = [i, j]
        i, j = bounary
        return s[i: j + 1]
  • 执行用时：9128 ms, 在所有 Python3 提交中击败了5.00%的用户
  • 内存消耗：20.9 MB, 在所有 Python3 提交中击败了23.99%的用户

Third Try​

2020-06-28

动态规划版本，效果一般般。依然是从最小到最大去遍历几乎所有可能的回文，说起来跟中心扩展法差不多的思路，但是速度还是慢了许多。

动态规划的核心tricks是从比较小的gap开始往外拓展，这样每次计算cache[i][j]的时候，往回找cache[i+1][j-1]都是必然被计算过的，想明白了这一点才能写出从小到大的动态规划出来。

另外对于每个i，cache[i][i]和cache[i][i+1]都是需要重点关注的，代表着奇数和偶数两种回文的中心区域，考虑条件要多一步，而不是两侧无脑减1知道长度为1。

anyway,这道题是最开始接触的前几道题，但是对于自己当时的解法一直不太满意，现在回首终于把常见的解法做完了，算是close one more case, 但求心安。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 从最小间隔往更大间隔走，这样每次处理的时候，小间隔都已经被处理过了，勉强算是达成了状态迁移。
        # 这个写法也是遍历所有可能的回文写法，算是很花费时间了。
        # 但是比起从大到小的写法，看来减少了对无关长字符串的计算

        if not len(s):
            return s

        cache = [[False] * len(s) for _ in range(len(s))]

        maxn = (1, 0, 0) # len, start, end
        for gap in range(0, len(s)):  # len 为 gap + 1, 比较方便计算
            for start in range(len(s) - gap):  # 这个比较头疼，改成while会方便许多
                end = start + gap
                if gap == 0:
                    cache[start][end] = True
                elif gap == 1:
                    cache[start][end] = s[start] == s[end]
                else:
                    cache[start][end] = cache[start + 1][end - 1] and s[start] == s[end]

                if cache[start][end] and gap + 1 > maxn[0]:
                    maxn = (gap + 1, start, end)
        plen, start, end = maxn 
        return s[start: end + 1]
  • 执行用时：3200 ms, 在所有 Python 提交中击败了37.75%的用户
  • 内存消耗：20.2 MB, 在所有 Python 提交中击败了8.70%的用户
  • 超时的动态规划版本

依然是使用从最大的最小的思路来查找，找到第一个就可以收工了。自以为能够加快速度，没想到竟然超时了。 问题应该在于如果本来就是小回文，很长的字符串反而会导致超多无效的计算。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 考虑使用动态规划法，一时半会真是挺难想到合理的方法
        # 从大往小找，找到直接跳出来，寻找过程中把走过的路都进行标记
        # wtf，竟然还超时了，这个写法那么烂吗
        if not len(s):
            return s
        cache = [["" for i in range(len(s))] for j in range(len(s))]
        for i in range(len(s)):
            cache[i][i] = True
        
        def checkPalindrome(start, end, s, cache):

            if cache[start][end] != "":
                return cache[start][end]
            if start > end:  # 忘记了导致提交错误
                return False 
            if start == end:
                return True
            if start + 1 == end and s[start] == s[end]:
                cache[start][end] = True
                return True
  
            cache[start][end] = checkPalindrome(start+1, end-1, s, cache) and s[start] == s[end]
            return cache[start][end]
            
        for lenp in range(len(s), 0, -1):  # [len(s), 0), 不包括0
            for start in range(0, len(s) - lenp + 1):  # start和end的选择挺麻烦的，这边界条件很容易出错
                end = start + lenp - 1 
                print(start, end, lenp)
                if checkPalindrome(start, end, s, cache):
                    return s[start: end + 1]

Second Try​

2020-06-28

对每个元素都从中间开始拓展延伸，计算能够延伸的最大宽度，结果其实是算出了所有可能的回文。注意点依然是对于每个i，中心延伸有两种可能：要么是作为奇数回文的中心，要么是作为偶数回文中的左侧(或右侧)，注意到这个corner case问题就得到了解决。


class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 最朴素的解法，每个点进行扩展，计算其为中心的最大回文
        # 回文有偶数和奇数，很容易只考虑奇数，对i点元素扩大只用是[i-1, i+1]，但其实也可以是[i-1, i]
        # 中心扩展，每次两边都扩展才算数
        if not len(s):
            return s

        def center_expand(left, right, s):
            if s[left] != s[right]:
                return (0, left, right)
            plen = right - left + 1
            while 0<= left - 1 and right + 1 < len(s) and s[left - 1] == s[right + 1] :
                left, right = left - 1, right + 1
                plen += 2
            return (plen, left, right)

        maxn = (1, 0, 0)  # len, start, end
        for i in range(1, len(s)):
            maxn = max(maxn, center_expand(i, i, s), key=lambda x: x[0])
            maxn = max(maxn, center_expand(i-1, i, s), key=lambda x: x[0])
        return s[maxn[1]: maxn[2]+1]
  • 执行用时：996 ms, 在所有 Python 提交中击败了62.65%的用户
  • 内存消耗：12.6 MB, 在所有 Python 提交中击败了13.04%的用户

First Try​

2020-06-01

也是暴力解法，从最长的字符子集往回走，相同长度的字符串都试一遍，一直找到的第一个就是最长的回文。回文判断方式也是存粹python写法。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 1:
            return s
        for i in reversed(range(1, len(s)+1)):
            start = 0
            while(start + i <= len(s)):
                col = s[start: start+i]
                if(col == col[::-1]):
                    return col
                start += 1

  • 执行用时 :5588 ms, 在所有 Python 提交中击败了11.12%的用户
  • 内存消耗 :12.9 MB, 在所有 Python 提交中击败了13.04%的用户