我正在做 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"
错误消息是超过时间限制。
这是为什么？我正在做一个动态规划解决方案，这应该是一个可以接受的答案。
最佳答案
您没有提前脱离内部循环，因此在所有情况下您仍在做 O(n²) 的工作。
考虑回文的中心必须有 'xx' 或 'x?x'。其中 x 是出现两次的任何字符，而 ?是任何字符。
对于某些病态情况，这可能不会改善最坏情况下的运行时间，但至少在您提供的示例中它应该为您节省大量计算。
关于algorithm - 寻找最长的回文子串(不是子序列)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47560660/