Leetcode 5: Longes回文子字符串

Question

我一直在研究LeetCode problem 5.最长的回文子串

给定一个字符串s，返回s中最长的回文子字符串。

但在大型测试用例上，我一直得到超过时限的信息。

我使用了以下动态编程：

dp[(i, j)] = True暗示s[i] to s[j]是回文。所以if s[i] == str[j] and dp[(i+1, j-1])设置为True，这意味着S[i] to S[j]也是回文。

如何提高此实现的性能？

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = {}      
        res = ""
        
        for i in range(len(s)):
            # single character is always a palindrome
            dp[(i, i)] = True
            res = s[i]
        
        #fill in the table diagonally
        for x in range(len(s) - 1):
            i = 0
            j = x + 1
            while j <= len(s)-1:
                if s[i] == s[j] and (j - i == 1 or dp[(i+1, j-1)] == True):
                    dp[(i, j)] = True
                    if(j-i+1) > len(res):
                        res = s[i:j+1]
                else:
                    dp[(i, j)] = False
                i += 1
                j += 1

        return res

Answer 1

我认为这个问题的评判系统有点太紧了，需要一些时间才能通过，改进后的版本：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = {}
        res = ""
        for i in range(len(s)):
            dp[(i, i)] = True
            res = s[i]

        for x in range(len(s)): # iterate till the end of the string
            for i in range(x): # iterate up to the current state (less work) and for loop looks better here
                if s[i] == s[x] and (dp.get((i + 1, x - 1), False) or x - i == 1):
                    dp[(i, x)] = True
                    if x - i + 1 > len(res):
                        res = s[i:x + 1]
        return res

Answer 2

下面是提高性能的另一个想法：

嵌套循环将检查在较小范围内DP值已经为False的许多情况。我们可以避免看大跨度，从内到外寻找回文，并停止延长跨度，因为它不再是回文。这个过程应该在源字符串中的每个偏移量重复，但这仍然可以节省一些处理。

那么大部分时间都被浪费的输入，是那些后面有很多相同字母的输入，比如"aaaaaaabcaaaaaaa“。这导致了许多迭代:每个"a“或"aa”都可能是回文的中心，但是“增长”每一个都是浪费时间。我们应该从一开始就考虑所有连续的"a“，然后从那里开始扩展。

您可以通过对相同的连续字母进行第一次分组来具体处理这些情况。因此，上述示例将被转化为4组: a(7)b(1)c(1)a(7)

然后，让每个组依次作为回文的中心。对于每一组，“扇出”可能包括一个或多个相邻的组在双方的“串联”。继续扇形，直到外部组的大小不一样，或者它们有不同的组大小。根据这个结果，您可以得到中心周围最大的回文数。特别是，当外部组的字母是相同的，但不是它们的大小时，您仍然在回文的外部包含那个字母，但是重复，对应于这两个不匹配的组大小中最小的一个。

这是一个实现。我使用命名元组来提高它的可读性：

from itertools import groupby
from collections import namedtuple

Group = namedtuple("Group", "letter,size,end")

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = ""
        x = 0
        groups = [Group(group[0], len(group), x := x + len(group)) for group in 
                   ("".join(group[1]) for group in groupby(s))]
        for i in range(len(groups)):
            for j in range(0, min(i+1, len(groups) - i)):
                if groups[i - j].letter != groups[i + j].letter:
                    break
                left = groups[i - j]
                right = groups[i + j]
                if left.size != right.size:
                    break
            size = right.end - (left.end - left.size) - abs(left.size - right.size)
            if size > len(longest):
                x = left.end - left.size + max(0, left.size - right.size)
                longest = s[x:x+size]

        return longest

Answer 3

或者，您可以尝试这种方法，它似乎比96%的Python提交更快。

 def longestPalindrome(self, s: str) -> str:
        N = len(s)
        
        if N == 0: 
            return 0
        
        max_len, start = 1, 0
        
        for i in range(N):
            df = i - max_len
            if df >= 1 and s[df-1: i+1] == s[df-1: i+1][::-1]:
                start = df - 1
                max_len += 2
                continue

            if df >= 0 and s[df: i+1] == s[df: i+1][::-1]:
                start= df 
                max_len += 1
        return s[start: start + max_len]