leetcode5 を解いてみた

方針

自分で1回はプロセスを考える。解けなくてもOK。
解けなかったときは、振り返ることが可能な程度まで言語化する。
※考え方おかしくない？というのがあればご指摘くださいまし。
※解けなかった、苦戦したものを記事にする。

問題紹介

問題は以下URL参照

最初の考え

• スマートな解法わかんないっぴ...
• とりあえず愚直にやってみるっぴ...

初回.py

class Solution:
    def longestPalindrome(self, s: str) -> str:
        tmp = []
        res = ""
        length = 0

        for i in range(len(s)):
            tmp = []

            for j in range(i,len(s)):
                tmp.append(s[j])
                reversed_tmp = list(reversed(tmp))
                if tmp == reversed_tmp and length < len(tmp):
                    length = len(tmp)
                    res = ''.join(tmp) 

        return res

思考中

• 案の定時間制限に引っかかった
• submitするたびに落ちるテストケースが変わるんだがなんぞや。実行時間ブレかな(´・ω・｀)
• 配列操作間引いたらもうちょいマシになるのかな？
  • とりあえず文字列でやってみたらどれぐらい良化するか見てみる。

second_try.py

class Solution:
    def longestPalindrome(self, s: str) -> str:
        tmp = ""
        res = ""
        length = 0

        for i in range(len(s)):
            tmp = "" #init for loop

            for j in range(i,len(s)):
                tmp = s[i:j+1]
                reversed_s = tmp[::-1]
                
                if tmp == reversed_s and length < len(tmp):
                    length = len(tmp)
                    res = tmp 

        return res

思考中2

• テストケース1/3 ⇨ 2/3通るようになったので速度は向上した(当たり前)
• これ以上はちゃんとアルゴリズム考えないとダメそう。
• 後は余分なサーチしてる部分を削って通るかどうかだな。

third_try.py

class Solution:
    def longestPalindrome(self, s: str) -> str:
        tmp = ""
        res = ""
        length = 0

        for i in range(len(s)):
            tmp = "" 
            if len(s)-i < length and res != 0:　　#add
                return res

            for j in range(i,len(s)):
                tmp = s[i:j+1]
                reversed_s = tmp[::-1]
                
                if tmp == reversed_s and length < len(tmp):
                    length = len(tmp)
                    res = tmp 

        return res

結果

third_try.pyで通ったけど実行速度ひどい...(´・ω・｀)

• solutionを見るとDPでやれるでって書いてるけどどうやったらDPでできるんだ状態(´・ω・｀)
• 文字列のど真ん中から回文をサーチしていくっていうやり方もあってなるほど...ってなった。
  • 今回通したブルートフォースよりかは計算量減りそう。

ほぼ初めてmedium解いたけど、解けるやつは解けるということがわかったのは嬉しい。
じわじわ精進します(´・ω・｀)