いいものをつくろう

CTOの日記

アルゴリズム

leetcode medium longest palindrome substring

投稿日:

import time
def timeit(func):
    def wrapped(*args, **kwargs):
        start = time.time()
        ret = func(*args, **kwargs)
        elapsed = time.time() - start
        print("elapsed: %s" % elapsed)
        return ret
    return wrapped

class Solution:
    @timeit
    def longestPalindrome(self, S: str) -> str:
        length = len(S)
        dp = [[0]*length for _ in range(length)]
        result = ""

        for offset in range(length):
            r = 0
            c = 0 + offset
            while r < length and c < length:
                if (r+1 < length and c-1 >= 0 and dp[r+1][c-1] == 1) or (c-1 < r+1):
                    if S[r] == S[c]: # This is palindrome
                        dp[r][c] = 1
                        if c+1 - r > len(result):
                            result = S[r:c+1]
                r+=1
                c+=1
        return result

 

みなさま、目標に近づいてますでしょうか?

おはようございます。

実行時間役O(n**3)の解

#-*- coding: utf-8 -*-
from typing import List
import math


class Solution:
    def is_parandrome(self, s):
        half_idx = math.ceil(len(s)/2)
        j = len(s)-1
        i = 0
        while i <= j:
            if s[i] != s[j]: return False
            i += 1
            j -= 1
        #print("is_parandrome(%s) == yes" % s)
        return True

    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1: return s
        ret = s[0]
        for i in range(len(s)):
            for j in range(i+1, len(s)):
                #print (i, j)
                y = self.is_parandrome(s[i:j+1])
                ret = s[i:j+1] if y and len(s[i:j+1]) > len(ret) else ret
        return ret

 

アルゴリズムとしては正解なのですが

実行時間オーバーなので最後の90/100ケース目あたりでパスしません。

どこを削ることができるでしょうか?( backtracking的枝刈りが有効か?)

それても全然違う考え方が必要でしょうか?(DPは有効か?)

 

経験からですが、substring問題とくればdpと考えてもいいでしょう

ではどうやってdpを組み立てればいいのでしょうか?

これは難しいですね。

とりあえず、string * stringのテーブル書いてみるのがいいんじゃないでしょうか。

そっからまたパターンを探していくのです。個人的にはとりあえず不正解でもいいのでたたき台を書き出して、

そこから正解の落とし込んでいくのが性に合っているようです。

とは行っても難しいでうよねー、毎回dp問題。よくそんなこと思いつくなーって解答を見ていつも思います

めげずに頑張りましょー

ちょっと説明が難しですが、内側がpalindromeだったら外側だけ常にチェックしていけばいい

という戦法です。

#-*- coding: utf-8 -*-
from typing import List
import math


class Solution:
    def longestPalindrome(self, s: str) -> str:
        #logging.basicConfig(level=logging.INFO, format="%(message)s")
        dp = [[-1]*len(s) for i in range(len(s))]
        # logging.debug("=== dp ===")
        # for row in dp:
        #     logging.debug(row)
        # logging.debug("=== main ===")
        for i in range(len(s)):
            for r in range(len(s)):
                for c in range(r, len(s)):
                    try:
                        x = dp[r][c+i]
                        if i == 0: dp[r][c+i] = 1
                        else: dp[r][c+i] = 0
                    except:
                        pass
                    break

        # logging.debug("=== dp ===")
        # for row in dp:
        #     logging.debug(row)
        if len(s) == 0: return s
        lp = s[0]
        # loop diagonally
        for i in range(len(s)):
            for r in range(len(s)):
                for c in range(r, len(s)):
                    try:
                        x = dp[r][c+i]
                        #logging.debug("(r, c+i) = (%d, %d)" % (r, c+i))
                        # 1-left-lower
                        try:
                            mid = dp[r+1][c+i-1]
                        except:
                            mid = 0
                        if s[r] == s[c+i] and (mid == 1 or mid == -1):
                            #logging.debug("--- hit ---")
                            dp[r][c+i] = 1
                            # update max
                            if c+i+1 - r > len(lp):
                                lp = s[r:c+i+1]
                        #logging.debug("mid[%s][%s](letters in the middle) is palandrome:%s" % (r+1, c+i-1, mid))

                    except:
                        pass
                    break

        # logging.debug("=== dp ===")
        # for row in dp:
        #     logging.debug(row)
        return lp

import logging
logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.basicConfig(level=logging.DEBUG, format="%(message)s")
s = "babad"
s = "cbbd"
# time-exceeded
s = "kyyrjtdplseovzwjkykrjwhxquwxsfsorjiumvxjhjmgeueafubtonhlerrgsgohfosqssmizcuqryqomsipovhhodpfyudtusjhonlqabhxfahfcjqxyckycstcqwxvicwkjeuboerkmjshfgiglceycmycadpnvoeaurqatesivajoqdilynbcihnidbizwkuaoegmytopzdmvvoewvhebqzskseeubnretjgnmyjwwgcooytfojeuzcuyhsznbcaiqpwcyusyyywqmmvqzvvceylnuwcbxybhqpvjumzomnabrjgcfaabqmiotlfojnyuolostmtacbwmwlqdfkbfikusuqtupdwdrjwqmuudbcvtpieiwteqbeyfyqejglmxofdjksqmzeugwvuniaxdrunyunnqpbnfbgqemvamaxuhjbyzqmhalrprhnindrkbopwbwsjeqrmyqipnqvjqzpjalqyfvaavyhytetllzupxjwozdfpmjhjlrnitnjgapzrakcqahaqetwllaaiadalmxgvpawqpgecojxfvcgxsbrldktufdrogkogbltcezflyctklpqrjymqzyzmtlssnavzcquytcskcnjzzrytsvawkavzboncxlhqfiofuohehaygxidxsofhmhzygklliovnwqbwwiiyarxtoihvjkdrzqsnmhdtdlpckuayhtfyirnhkrhbrwkdymjrjklonyggqnxhfvtkqxoicakzsxmgczpwhpkzcntkcwhkdkxvfnjbvjjoumczjyvdgkfukfuldolqnauvoyhoheoqvpwoisniv"
ans = Solution().longestPalindrome(s)
logging.info(ans)

よっしゃこれでいけるだろうと思ったのですが、

多分最初の初期化の処理が結局O(n**3)になっちゃっているので

処理時間超過しているのではなんて思ったのですが、最後のループはbreakで常に終了するのでO(n**2)だと

思っています。

ちょっとここで他の人たちの解答を見ることにしました。

あまり悩んで一つの問題に時間をかけるよりは一定時間悩んだら次に行くようにします。

斜めにループできますか?プログラミング で書いた通り斜めの操作とい技を

覚えました。これを元に、

ではこれで longest palindrome substringを再実装していきます。

import logging
class Solution:
    def longestPalindrome(self, S: str) -> str:
        logging.basicConfig(level=logging.INFO, format="%(message)s")
        logging.debug("palandrome(%s)" % S)
        dp = [[0]*len(S) for _ in range(len(S))]
        for i in range(len(S)):
            dp[i][i] = 1
        result = ""

        for offset in range(len(S)):
            r = 0
            c = 0 + offset
            while r < len(S) and c < len(S):
                #logging.debug(dp[r][c], end=",")
                if (r+1 < len(S) and c-1 >= 0 and dp[r+1][c-1] == 1) or (c-1 < r+1):
                    if S[r] == S[c]:
                        logging.debug("oh yes, this is palandrome")
                        if c+1 - r > len(result):
                            result = S[r:c+1]
                        dp[r][c] = 1
                r+=1
                c+=1
        return result

とコーディングして、いざ提出してみると

1000文字ちょうどのサンプルで弾かれてしまいました

ということで、

timeitで時間を測って削られるだけ削りました

0.4秒から0.27秒まで落とせたので、自信を持って提出、ドリャ!

import time
def timeit(func):
    def wrapped(*args, **kwargs):
        start = time.time()
        ret = func(*args, **kwargs)
        elapsed = time.time() - start
        print("elapsed: %s" % elapsed)
        return ret
    return wrapped

class Solution:
    @timeit
    def longestPalindrome(self, S: str) -> str:
        length = len(S)
        dp = [[0]*length for _ in range(length)]
        result = ""

        for offset in range(length):
            r = 0
            c = 0 + offset
            while r < length and c < length:
                if (r+1 < length and c-1 >= 0 and dp[r+1][c-1] == 1) or (c-1 < r+1):
                    if S[r] == S[c]: # This is palindrome
                        dp[r][c] = 1
                        if c+1 - r > len(result):
                            result = S[r:c+1]
                r+=1
                c+=1
        return result

やっと通りました。

もちろんtimeitの部分はコメントアウトして提出しました

驚いたのは、len(S)の部分が多用されていたのですが、これは事項時間に影響しないと

考えていたのですが、実はloopでO(n**2)でlen(S)が実行されるのは効いていたようです。

これからは細かい点ですが、len(S)は実行時間を食う対象として考えます。

で、パフォーマンスなのですが、以下の通り最低ラインなので

ここはもう一踏ん張りして、最適な解を取りに行きたいと思います。

ということで、一応自分の頭で

よぎった、外側に拡張していアイデアをちゃんと書けている人が沢山いるので

彼らか学び、次回は自分でもかけるようになるべく

練習して言いたいと思います。

逆に言えば自分の弱みは、アイデアを思いつてもそれをスラスラとコードに書き落とすことができないという

コーディング・実装力のなさですこれは練習で補っていきたいと思います

参考にするソースはこちらですね

一個一個愚直に拡張していくパターンです。

最初に思いついた時は具体的な速度O(what)になるのか?

ぼんやりでストップするのではなく、O(what)になるイメージをちゃんと掴めるところまで

実装をイメージできるかは非常に大切で、ここまでイメージが湧かないと面接などの限られた時間で能力を示すには意味がないと思います。

今回であればO(n)でなめてO(n)で拡張する(expand)するイメージをもつことでO(n**2)で計算できる

"""
dp使わずに拡大していく方法
"""
class Solution:
    def expand_palindrome(self, S, i):
        l = i - 1
        r = i + 1
        result = S[i]
        while l >= 0 and r < len(S) and S[l] == S[r]: # check l and r within valid range
            # this is palindrome
            if r+1-l > len(result):
                result = S[l:r+1]
            l -= 1
            r += 1
        return result

    def expand_palindrome_2(self, S, i, j):
        l = i - 1
        r = j + 1
        if i < 0 or j >= len(S): return ""
        if S[i] != S[j]: return ""
        result = S[i:j+1]
        while l >= 0 and r < len(S) and S[l] == S[r]: # check l and r within valid range
            # this is palindrome
            if r+1-l > len(result):
                result = S[l:r+1]
            l -= 1
            r += 1
        return result

    @timeit
    def longestPalindrome(self, S: str) -> str:
        if len(S) <= 1: return S
        result = S[0]
        # palindrome starting with 1 char
        for i, c in enumerate(S):
            tmp = self.expand_palindrome(S, i)
            if len(tmp) > len(result):
                result = tmp
        # palindrome starting with 1 char
        for i, c in enumerate(S):
            tmp = self.expand_palindrome_2(S, i, i+1)
            if len(tmp) > len(result):
                result = tmp
        return result

上記の実装ももう少し削れるとは思いますが

ご覧のように、前よりはよくなりました。

 

このlongest palindrome substringという問題は

かなりてこづりました。しかしながら全部自分で実装することろまで持って行ったことで

1。longest最長とか聞かれたら、DPを連想し、とりあえずDP表を作る、という持っていき方

2。斜めの操作

3。今回であればO(n)でなめてO(n)で拡張する(expand)するイメージをもつことでO(n**2)で計算できる

 

とうい3つの学びを習得できました

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.