Leetcode，最长回文子字符串

Question

这是一个链接

给定一个字符串s，返回s中最长的回文子字符串。如果字符串的反向与原始字符串相同，则该字符串称为回文字符串。

示例1：

输入:S= "babad“输出："bab”解释："aba“也是一个有效的答案。

示例2：

投入:S= "cbbd“输出："bb”

from collections import defaultdict
    

def is_palindrome(s):
    return s == s[::-1]


def solve(s):
    seen = defaultdict(list)
    found = ''
    for i, char in enumerate(s):
        if seen[char]:
            for j in seen[char]:
                ss = s[j : i + 1]
                if is_palindrome(ss):
                    found = max(ss, found, key=len)
                    break
        seen[char].append(i)
    if not found:
        found = s[0]
    return found

Answer 1

在强力O(N^2)解上做得很好。当然，它仍然是O(N^2)，但是运行速度要快得多，特别是对于随机字符的短字符串。如果您对线性解决方案感兴趣，就是这里 (尽管它不是您可以在5分钟内实际发明的东西)。

一些面试官可能会抱怨命名：found听起来像是一个布尔名称，用于判断是否找到回文，而s和ss则什么也不说。想出一个合适的名字可能需要一些时间，但如果你告诉面试官你为什么要花时间，这将是一个很大的好处:命名在产品代码中是非常重要的。

此外，您没有指定约束，因此如果字符串为空，此解决方案就会中断。在一次真正的面试中，一定要检查所有的问题和制约因素，这是非常重要的。能够找到那些角落的案件是主要的事情之一，这样的访谈是为了检查。