【アルゴリズム脳トレ】leetcode medium 5 longest palindrome substring

こんにちは

今回の学びは

・palindromeは文字expand方式で解け

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

文字列 ababcなどが与えられて、最も長いpalindrome substring

は何になりますか？という問題

どうやら以前、二ヶ月前に挑戦している模様。

模様。つまりほぼ完全に忘れてしまっている。。

まぁ、これまでいろんなmediumの問題にも触れて

今回はどれだけtimeを縮められるか楽しみでもあった。

前回のpalindromeの問題(leetcode easy 125 valid palindrom2)を応用できたりもするだろう、と考えていた。

ここで文字列の組み合わせがi, jのループでO(N^2)となる

さらに前回のpalindromeの問題(leetcode easy 125 valid palindrom2)の両端から交差操作のアルゴでいくとO(N)で

結局O(N^3)の解となる。

それ以上のものができんかね〜と

考えたわけですが、これが思いつかない。

時間もすぎるのでO(N^3)を実装しはじめました

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　O(N^3)

実際の実装はこちら

class Solution_tle:
    def isPalindrome(self, s: str) -> bool:
        # l, r point
        # ignore non-alphabet
        # case insensitive
        length = len(s)
        if s == None: return False
        if s == "": return True

        l = 0
        r = length-1

        while l <= r:
            if not (s[l].isalpha() or s[l].isnumeric()) : l+=1; continue;
            if not (s[r].isalpha() or s[r].isnumeric()): r-=1; continue;
            if s[l].lower() != s[r].lower(): return False
            l += 1
            r -= 1
        return True

    def longestPalindrome(self, s):
        if s == "": return ""
        length = len(s)
        longest = ""
        for i in range(length):
            for j in range(i, length):
                if self.isPalindrome(s[i:j+1]):
                    if len(s[i:j+1]) > len(longest):
                        longest = s[i:j+1]
        return longest

上記の実装ですが、

予想通りTLEを起こしました。テストケース的には最後の方まで残ったので一部の望みはあったのでうが

やはりTLEです。

# 1015am TLE
# 89 / 103 test cases passed.
# この問題に関しては成長してない、私のシナプスが。
# 今回で克服したい。
# O(N^3) -> O(N^2)にもっていけないか？

と、振り出しにもどったわけですが、しばらく考えるも思いつかづ

答えをみることしました。

そして、expandしてpalindromeをみつけるというアイデアに。

あっ

これやったな〜

なんで、また忘れているんだろう

とりあえず、ここは

・palindromeは文字expand方式で解け

という

風に今回おぼえてしまします。

これでわすれないでしょう。

アイデアがあれば実装は簡単でした

class Solution:
    def get_palindrome(self, S: str, i: int, j: int) -> bool:
        # i is starting index
        length = len(S)
        ans = ""
        while i >= 0 and j < length:
            if S[i] == S[j]:
                ans = S[i:j+1]
            else:
                break
            i -= 1
            j += 1
        return ans

    def longestPalindrome(self, s):
        if s == "": return ""
        length = len(s)
        longest = ""
        for i in range(length):
            palindrome = self.get_palindrome(s, i, i)
            if len(palindrome) > len(longest):
                longest = palindrome
            palindrome = self.get_palindrome(s, i, i+1)
            if len(palindrome) > len(longest):
                longest = palindrome
        return longest

実装後です。timespace analysis (時間とスペースの分析）は　O(N^2)

これで二ヶ月ぶりにSuccessを手にいれて時間は少しはやくって上位50％となりました。

一応O(N^2)でも上位50%ということは、O(N^2)がほとんどの人が考える解答ということなのでしょう。

ひとまずよしです。

では上位２０％の人の解答もみたくなりました。

https://leetcode.com/problems/longest-palindromic-substring/discuss/377074/Python-dp

dpですか。ちょっと、急ぎなので今日はここまで。では！

まとめ

・palindromeは文字expand方式で解け

以上です