Decode Ways

Q: Decode Ways の時間計算量は何ですか？

ボトムアップの解法では各桁を一度ずつ読み取り、一定の作業量で済みます。時間計算量は O(n) 、追加の空間計算量は O(1) です。メモ化再帰も時間計算量は O(n) ですが、空間計算量は O(n) です。単純な再帰は指数時間です。1だけからなる文字列では、呼び出し回数は 1.618^n のように増加します。

Q: Decode Ways ではゼロをどのように扱いますか？

0 は単独では文字にならないため、直前の数字と組み合わせて 10 または 20 として扱う必要があります。1または2の後にある場合に限り、2桁前のカウントを加え、それ以外の場合は加えません。先頭の 0 、連続する2つのゼロ、または3から9の後にある 0 は、いずれも0になります。

ふつう動的計画法

+10

大文字のメッセージは、A = 1、B = 2、以下同様にZ = 26として符号化され、符号の間に区切りを入れずに書かれています。数字列sが与えられたとき、それを生成できるメッセージの数を返してください。

文字は1桁または隣り合う2桁から読み取り、符号が0で始まることはありません。06は6ではなく、単独の0も文字ではありません。読み取れる方法がない場合は、0を返してください。

関数

numDecodings(s: string) → integer

sstring: デコードする数字列
戻り値integer: s にエンコードされる文字メッセージの数

制約

1 ≤ s.length ≤ 100
sには数字の0から9のみが含まれ、0で始まる場合があります。
s のすべての接頭辞と接尾辞の読み取り数は 2³¹ 未満なので、答えと計算途中で求めるすべての個数は符号付き32ビット整数に収まります。

例

入力: s = "2611"
出力: 4
説明: 4つの読み方は2 6 1 1（BFAA）、26 1 1（ZAA）、2 6 11（BFK）、26 11（ZK）です。61は26より大きいため、中央の数字が組み合わさることはありません。

入力: s = "1203"
出力: 1
説明: 0は、それより前にある2と組み合わさって20になる必要があり、その結果1 20 3（ATC）になります。先に12を読むと、0が単独で残り、03は0で始まります。

入力: s = "06"
出力: 0
説明: 最初の文字は0で始まる必要があります。0だけでは文字ではなく、06はコードではないため、この文字列を与えるメッセージはありません。

発展問題

もしsが、1から9までの任意の数字を表す*も保持できるとしたらどうでしょうか？10^9+7を法として、O(n)時間で読み取り方の数を数えられますか？

ヒント

1つずつ開いてください。開くたびに少しずつ答えに近づきます。

3個中0個を表示

解説

各桁は単独で1文字を表すか、隣の桁と組み合わせるため、読み方の数はフィボナッチ数列のように増えます。1が45個ある場合、その数は1836311903通りです。すべて列挙するのは現実的ではありませんが、読み方を完成させる方法は到達した位置だけで決まるため、各位置を一度だけ数えれば十分です。0は10または20の末尾にしかなれません。

再帰を使って両方の読み方を試してみましょう

正しいが、最大のテストでは終わらない

考え方

インデックス i で、0 は文字の先頭にならないため、その経路では読み取りができません。それ以外の場合は、1桁を読み取り、残りを i+1 から数えます。2桁の数字が10から26になる場合は、2桁とも読み取り、i+2 から数える方法もあります。この2つの選択肢では最初の文字が異なるため、重複せずに数を足せます。末尾に到達すると、1つの読み取りが完成します。

何も記憶されないため、呼び出し回数はフィボナッチ数列の規則に従います。1が45個あると、呼び出し回数は約 5 × 10^9 回です。答えが0の場合も速くはなりません。1が44個、3が55個あり、最後に 0 があると、呼び出し回数は約 10^11 回になります。これは、1が続く部分のあらゆる読み取りが最後の桁で初めて行き止まりになるためです。

アルゴリズム

waysFrom(i) は、インデックス i 以降の数字の読み方の数を数えます。
文字列の末尾では、1 を返します。0 の場合は、0 を返します。
それ以外の場合は、waysFrom(i+1) を返し、数字 i と i+1 が 26 以下の数を形成する場合は、waysFrom(i+2) を加えます。
答えは waysFrom(0) です。

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

メモ化を使った再帰

考え方

再帰では、同じ問いを何度も繰り返します。"11111"では、インデックス3からの個数が1 1 1の後、11 1の後、そして1 11の後に必要になりますが、インデックス3以降の数字だけで決まるため、毎回同じです。各個数は初めて計算したときに保存し、0は実際の個数なので、まだ計算していないスロットには-1を設定します。

n個の位置があり、それぞれ定数時間の処理で1回ずつ計算されるため、時間計算量はO(n)です。メモと呼び出しスタックにはO(n)の空間が必要で、呼び出しの深さは最大100です。

アルゴリズム

memo を -1 で埋め、各インデックスに 1 つずつ割り当てます。
waysFrom(i) では、文字列の末尾で 1 を返し、memo[i] が -1 でない場合は memo[i] を返します。
それ以外の場合は、通常の再帰と同様に数を数え、0 も含めてその数を memo[i] に保存し、それを返します。

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

2 つのカウンターを使ったボトムアップ

考え方

代わりに、接頭辞の数を数えます。ways(i)を、最初のi桁の読み方の数とします。最後の文字は、桁i-1だけの場合（1から9である必要があり、ways(i-1)通りの読み方が残ります）か、桁i-2とi-1を組み合わせた場合（10から26である必要があり、ways(i-2)通りの読み方が残ります）のどちらかです。条件を満たす部分を足します。空の接頭辞の読み方は1通りなので、ways(0) = 1です。

"1203"では、数は1、2と進み、0のところで1に戻ります。20だけが有効で、2の前の数を引き継ぐためです。3は単独で使えるので、数は1のままです。各数は2つ前の値を参照するため、表の代わりに2つの変数を使えます。時間計算量はO(n)、空間計算量はO(1)です。

アルゴリズム

twoBack = 0 と oneBack = 1 を、空の接頭辞の個数として設定します。
各インデックス i について、数字 i が 0 でなければ current を oneBack に設定し、そうでなければ 0 に設定します。
i ≥ 1 であり、数字 i-1 が 0 ではなく、数字 i-1 と i の組み合わせが最大 26 である場合、twoBack を加算します。
シフトします。twoBack = oneBack とし、次に oneBack = current とします。
oneBack を返します。

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

落とし穴と境界ケース

0を文字として扱ったり、06を6として扱ったりすること。"30"、"100"、"06"はいずれも読み方が0通りです。
2桁のまとまりを≤ 26だけで判定すること。05は数としては5ですが、コードではないので、最初の桁が0でないことを確認してください。
未使用のメモ欄を0で初期化すること。読み方が0通りの位置は保存済みとして数えられません。そのため、1が44個、3が55個、最後に0がある場合、呼び出し回数は約10^11回に戻ってしまいます。
インデックス0より前の桁を読み取ること。2桁の判定はi ≥ 1でガードしてください。Pythonではs[-1]はエラーにならず、最後の桁を読み取ります。
sを1つの数値に変換すること。100桁の数値はどの整数型にも収まりません。また、答えを変える先頭のゼロも失われます。

よくある質問3

Decode Ways の時間計算量は何ですか？

ボトムアップの解法では各桁を一度ずつ読み取り、一定の作業量で済みます。時間計算量は O(n)、追加の空間計算量は O(1) です。メモ化再帰も時間計算量は O(n) ですが、空間計算量は O(n) です。単純な再帰は指数時間です。1だけからなる文字列では、呼び出し回数は 1.618^n のように増加します。

Decode Ways は Climbing Stairs とどのように関連していますか？

どちらも、1段と2段のステップで階段を上る方法の数を数えます。Climbing Stairsではすべてのステップが可能なので、その数はフィボナッチ数になります。Decode Waysでは、1桁のステップには1から9、2桁のステップには10から26が必要なので、それぞれの条件を満たす場合にのみ各項が加算されます。

Decode Ways ではゼロをどのように扱いますか？

0は単独では文字にならないため、直前の数字と組み合わせて10または20として扱う必要があります。1または2の後にある場合に限り、2桁前のカウントを加え、それ以外の場合は加えません。先頭の0、連続する2つのゼロ、または3から9の後にある0は、いずれも0になります。

def numDecodings(s):
    # ここにコードを書いてください

テスト #1

テスト #2

テスト #3

引数

s = "2611"

期待される出力

Decode Ways

関数

制約

例

ヒント

解説

再帰を使って両方の読み方を試してみましょう

メモ化を使った再帰

2 つのカウンターを使ったボトムアップ

落とし穴と境界ケース

よくある質問3

似た問題