如何快速检查一个字符串中是否包含回文子串

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。

- Clock Slave

---

一个简单的提示：从开头和结尾同时开始，逐个比较每个字母，直到达到中间位置。 - Aethernite

检查Manacher算法以在O（N）中找到所有子回文。您可以修改算法以在找到第一个回文时返回true。 - Aethernite

Answer 1

由于您只需要长度大于一的回文字符串，因此只需查找模式aa或aba。 这可以在单个线性遍历中完成，最坏情况下需要N-1+N-2次比较（在最好情况下只需要1次比较）。

- user1196549

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))

- user2390182