最長のパリンドローム部分文字列を見つける（サブシーケンスではない）

Question

私はLeetcodeに関する質問をとしています。Longeest Palindromicサブストリングを検索してください。入力がをbabad場合、出力は、BAB又はABAことができ、例えば

。

OR

入力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" 

エラーメッセージは時間制限を超えています。

これはなぜですか？私は受け入れられた答えでなければならないDynamic Programmingソリューションをやっています。

Answer 1

あなたは内部のループを早期に中断しているわけではないので、あなたはまだすべてのケースでO（n²）の仕事をしています。

palindromeには、中央に 'xx'または 'x？x'のいずれかが必要であるとします。ここで、xは2回現れる文字です。任意の文字です。

これはおそらくいくつかの病理学的なケースでは最悪の場合の実行時間を改善しませんが、少なくとも提供した例では多くの計算量を節約するはずです。