最长回文：什么可能会减缓我的DP解决方案？

Question

我的解决方案不知何故通过了他们所有的测试用例，但运行超过了时间限制。我已经实现了一个基于DP的解决方案，不知道什么可能需要额外的时间。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        table = [[True] for i in range(len(s))]
        best = (0,1)
        for i in range(len(s) - 1):
          for j in range(0, len(s) - i -1):
            size = i + 1
            shift = j
            diag = table[j + 1][i-1]
            eq = s[shift] ==  s[shift + size]
            table[j].append(diag and eq)
            if diag and eq: best = (shift,  shift + size + 1)
        return s[best[0]:best[1]]

Answer 1

这里有一种解决这个问题的方法，
首先定义一个窗口大小（比如滑动窗口），然后尝试用这个窗口大小来分割字符串，并检查它是否是回文。

如果你没有任何解决方案到达终点，只需减小窗口大小并重新开始，直到找到回文。

下面是一个示例代码：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        window_size = len(s)
        while True:
            for i in range(0, (len(s) - window_size) + 1):
                if s[i : i + window_size] == s[i:i + window_size][::-1]:
                    return s[i : i + window_size]
            else:
                window_size -= 1