【アルゴリズム脳トレ】leetcode medium 91 decode ways

こんにちは

今回の学びは

・難しすぎると感じたらそれは、間違いなんじゃないかな。と考えるようにしてみよう。もうすこし噛み砕くと。　dp表の埋めかたとして、最初は目的変数を、それでアイデアが生まれなかったら目的変数を構成する要素を書き出せ

問題は。。。

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

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

最初に

ちゃんと再帰でのブルートフォースが思いついたのはいいですね。

O(2^(n/2)) => O(2^n) = １文字とるパターンと２文字とるパターンでの再帰。

そのあと

dpかなと思って表を考えに行くのですが、

数字で最終的な数を埋めていく、以下のような感じで考えると

全然閃きません、むしろ、俺は正しいことを考えているのか？なんかむずいぞ

と自問自答し始めます。多分、

難しすぎると感じたらそれは、間違いなんじゃないかな。と考えるようにしてみよう。

最初の組み合わせの最終的な数をdpにはめていく、イメージが正解へと広がらなかった

パターンはこちらみたいな感じ

で！これを

具合的にこんか感じで考え始めた瞬間！

すぐ、閃いたよね。これが正解への道だと。この正解への糸口を掴んだ時の感覚は

非常に問題解決者にとって嬉しいです！

で、

最初の組み合わせの数、というのは具体例を隠しているんですが、それでもdp考える上では

答えを持ってくるのが常套手段なので、いいとは思うのですが、それで難しいと感じたら

まずは、もっと具体的に考える、今回の場合は組み合わせのパターンを書き出してみる

というよなことをした方が、アイデアは思いつきやすいですね。

これは勉強になりました。

難しすぎると感じたらそれは、間違いなんじゃないかな。と考えるようにしてみよう。

＝＞ちょい改め

dp表の埋めかたとして、最初は目的変数を、それでアイデアが生まれなかったら目的変数を構成する要素を書き出せ

という学びにしておきます

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

pseudocode（擬似コード）をかいてみますか。

。。。

実際の実装はこちら

class Solution:
    """
    1.  O(2^(n/2)) => O(2^n) = １文字とるパターンと２文字とるパターンでの再帰
    2.

    """
    @timeit
    def numDecodings(self, s: str) -> int:
        # non-empyt is guranteeed by the problem description
        length = len(s)
        dp = [0] * length
        dp[0] = 1
        if len(s) == 1 and s == "0": return 0
        if len(s) == 1: return 1
        if len(s) == 2: return 2
        dp[1] = 2

        # assuming that all the input are sanitized
        def dp_print():
            for row in dp:
                logging.debug(row)
        def dp_get(i, default=0):
            if i < 0 or i >= length: return default
            return dp[i]

        for i in range(2, length):
            if int(s[i-1] + s[i]) <= 26:
                dp[i] = dp_get(i-2) + dp_get(i-1)
            else:
                dp[i] = dp_get(i-1)
        dp_print()
        return dp[i]

これでは"10"のケースで通らなかった

どうやら"0"がくせもので、いろいろパターンをかんがえてやらないといけなかった

でも、それでとおりましたので

大枠のdpの考え方は正解です。

最終的な実装はこちらでスピードも上位３％ととてもよかったです。

class Solution:
    def numDecodings(self, s: str) -> int:
        # non-empyt is guranteeed by the problem description
        length = len(s)
        dp = [0] * length
        dp[0] = 1
        if len(s) == 1 and s == "0": return 0
        if len(s) > 0 and s[0] == "0": return 0
        if len(s) == 1: return 1

        def dp_get(i, default=0):
            if i < 0 or i >= length: return default
            return dp[i]

        for i in range(1, length):
            if s[i-1] == "0" and s[i] == "0": return 0
            x = int(s[i-1] + s[i])
            if 10 <= x and x <= 26:
                if s[i] == "0":
                    dp[i] = dp_get(i-2, default=1)
                else:
                    dp[i] = dp_get(i-2, default=1) + dp_get(i-1, default=1)
            elif x % 10 == 0:
                return 0
            else:
                dp[i] = dp_get(i-1, default=1)
        return dp[i]