方針

自分で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解いたけど、解けるやつは解けるということがわかったのは嬉しい。
じわじわ精進します(´・ω・｀)