检查字符串是否包含回文子串的最快方法

Question

我试图检查一个字符串是否包含任何长度 > 1 的子字符串，这是一个回文。（请注意，这与检查整个字符串是否为回文串不同。）我能够编写一个函数来查找偶数或奇数长度的回文子串；我已尽我所能对其进行优化，但我的代码超出了一些测试用例的时间限制。

如何改进算法以使其更快？

def findPalindrome(s):
    ans = ""
    for i in range(len(s)):
        for k in range(2):
            temp = str_parser(s, i, i + k)
            if len(temp) > len(ans) and len(temp) > 1:
                return 1
    return 0


def str_parser(s, l, r):
    while l >= 0 and r < len(s):
        if s[r] == s[l] and len(s[l:r+1]) > 1:
            return s[l:r+1]
        else:
            l -= 1
            r += 1
    return ''

findPalindrome如果输入字符串包含回文，该函数返回 1，否则返回 0。

Answer 1

由于您只是要求长度大于 1 的回文，因此查找模式aa或aba. 这是在单个线性通道中完成的，N-1+N-2最坏的情况下1进行比较（最好的情况下进行比较）。

Answer 2

正如已经指出的，您所要做的就是检查是否存在长度为 2 或 3 的回文：

def findPalindrome(s):
    return any(x==y for x,y in zip(s, s[1:])) or any(x==y for x,y in zip(s, s[2:]))

或者更简洁：

return any(c in s[i+1:i+3] for i, c in enumerate(s))