寻找最长回文子串（不是子序列）

Question

我正在做Leetcode上的一个问题，题目是：找到最长回文子串。

例如，如果输入为babad，则输出可以是bab或aba。

或者

如果输入为cbbd，则输出为bb。

我相当确定已经想出来了，这是我的代码......

def longestPalindrome(self, s):

    n = len(s)

    # Empty matrix.
    table = [[False for i in range(n)] for j in range(n)]

    # Identity matrix.
    for i in range(n):
        table[i][i] = True

    max_len = 0
    start = 0
    finish = 0

    for sil in range(2, n+1):
        for i in range(n-sil + 1):
            j = sil + i - 1
            if sil == 2:
                if s[i] == s[j]:
                    table[i][j] = True
                    max_len = j-i
                    start = i
                    finish = j
            else:
                if s[i] == s[j] and table[i+1][j-1]:
                    table[i][j] = True

                    if (j - i) > finish-start:
                        max_len = j - i
                        start = i
                        finish = j

    return s[start:finish+1]

它适用于大多数情况，但当字符串非常长时会出现问题。我正在提交我的代码，但在以下情况下失败了...

"esbtzjaaijqkgmtaajpsdfiqtvxsgfvijpxrvxgfumsuprzlyvhclgkhccmcnquukivlpnjlfteljvykbddtrpmxzcrdqinsnlsteonhcegtkoszzonkwjevlasgjlcquzuhdmmkhfniozhuphcfkeobturbuoefhmtgcvhlsezvkpgfebbdbhiuwdcftenihseorykdguoqotqyscwymtjejpdzqepjkadtftzwebxwyuqwyeegwxhroaaymusddwnjkvsvrwwsmolmidoybsotaqufhepinkkxicvzrgbgsarmizugbvtzfxghkhthzpuetufqvigmyhmlsgfaaqmmlblxbqxpluhaawqkdluwfirfngbhdkjjyfsxglsnakskcbsyafqpwmwmoxjwlhjduayqyzmpkmrjhbqyhongfdxmuwaqgjkcpatgbrqdllbzodnrifvhcfvgbixbwywanivsdjnbrgskyifgvksadvgzzzuogzcukskjxbohofdimkmyqypyuexypwnjlrfpbtkqyngvxjcwvngmilgwbpcsseoywetatfjijsbcekaixvqreelnlmdonknmxerjjhvmqiztsgjkijjtcyetuygqgsikxctvpxrqtuhxreidhwcklkkjayvqdzqqapgdqaapefzjfngdvjsiiivnkfimqkkucltgavwlakcfyhnpgmqxgfyjziliyqhugphhjtlllgtlcsibfdktzhcfuallqlonbsgyyvvyarvaxmchtyrtkgekkmhejwvsuumhcfcyncgeqtltfmhtlsfswaqpmwpjwgvksvazhwyrzwhyjjdbphhjcmurdcgtbvpkhbkpirhysrpcrntetacyfvgjivhaxgpqhbjahruuejdmaghoaquhiafjqaionbrjbjksxaezosxqmncejjptcksnoq"

错误提示为“时间限制超出”。为什么会出现这种情况呢？我正在使用动态规划解决方案，应该是一个被接受的答案。

- buydadip

Answer 1

你没有提前跳出内部循环，因此在所有情况下仍在进行O(n²)的工作。

考虑到回文必须在其中心具有'xx'或'x?x'。其中x是任何出现两次的字符，而？是任何字符。

这可能不会改善某些病态情况的最坏运行时间，但至少在你提供的示例中，它应该节省大量计算。

- Imran