【アルゴリズム脳トレ】leetcode medium647 palindromic substring

こんにちは

今回の学びは

・panlindromeはパターンをおぼえれば速攻解けた

問題は。。。

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

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

さっきの問題medium 5 longest palindrome substring をやったあとなら

すごく簡単に感じあした。

ほぼ一緒だからです。

ということで

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

実際の実装はこちら

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

    def countSubstrings(self, s: str) -> int:
        if s == "": return ""
        length = len(s)
        ans = 0
        for i in range(length):
            palindrome = self.get_palindrome(s, i, i)
            ans += palindrome
            palindrome = self.get_palindrome(s, i, i+1)
            ans += palindrome
        return ans

この問題は5分でとけました。

他の問題が基礎になり、応用問題は楽勝になった感じです

medium問題でもその問題の基礎easy問題が解ければ

すぐに解けるあるいは解きやすいとい例はいくらでも経験してきました。

同じ系統、

今回の場合はpalandromicは制覇した気持ちになりました

本当は

hard問題解いてから言わないといけないことですかね。

こちらはpalandromic sebstringではなくてsubsequenceときましたよ！

あとはhardなshortest palandromeとかもありますね。

頑張ってください

まとめ

・panlindromeはパターンをおぼえれば速攻解けた

以上です