Pythonで数字列をアルファベットにデコードする方法の数を求める（動的計画法）

問題の概要

「A」から「Z」までの英字が、以下のような対応表を使って数字にエンコードされているとします。

• 'A' → 1
• 'B' → 2
• ...
• 'Z' → 26

ここで、数字のみで構成された空でない文字列が与えられたとき、その文字列が何通りの方法でデコードできるかを求めます。

例えば、文字列が「12」だった場合、「AB」（1= A、2 = B）としても「L」（12 = L）としても解釈できるため、デコード方法は2通りあります。したがって答えは2となります。

もう一つの例として「226」を見てみましょう。これは「BZ」（2, 26）、「VF」（22, 6）、「BBF」（2, 2, 6）の3通りにデコードできるため、答えは3になります。

解き方のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解けます。手順は以下の通りです。

1. n を文字列 s の長さとし、長さ n の DP 配列 dp をすべて 0 で初期化します。
2. s[0] が '0' でない場合、dp[0] := 1 とします（先頭が0の場合はデコード不可能です）。
3. i を 1 から n-1 までループさせます。
   • x := s[i] を整数化した値、y := s[i-1:i+1]（2桁の部分文字列）を整数化した値とします。
   • x が 1 以上 9 以下の場合：1桁として有効なので、dp[i] += dp[i-1]。
   • y が 10 以上 26 以下の場合：2桁として有効なので、i-2 >= 0 なら dp[i] += dp[i-2]、そうでなければ dp[i] += 1。
4. 最後に dp の末尾要素を返します。

このアルゴリズムの計算量は O(n)、必要なメモリも O(n) であり、非常に効率的です。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def numDecodings(self, s):
        n = len(s)
        dp = [0 for i in range(n)]
        if s[0] != '0':
            dp[0] = 1
        for i in range(1, n):
            x = int(s[i])
            y = int(s[i-1:i+1])
            if x >= 1 and x <= 9:
                dp[i] += dp[i-1]
            if y >= 10 and y <= 26:
                if i - 2 >= 0:
                    dp[i] += dp[i-2]
                else:
                    dp[i] += 1
        return dp[-1]

ob1 = Solution()
print(ob1.numDecodings("226"))

入力

"226"

出力

3

コードのポイント

この実装における重要なポイントを整理します。

• 先頭が「0」の場合： 「0」には対応するアルファベットが存在しないため、dp[0] は 0 のままとなり、結果的に全体のデコード数も 0 になります。
• 1桁チェック（x >= 1 かつ x <= 9）： 現在の桁が 1〜9 の範囲内であれば、単独の文字としてデコード可能です。「0」単体は無効であることに注意してください。
• 2桁チェック（y >= 10 かつ y <= 26）： 直前の桁と組み合わせた2桁の数値が 10〜26 の範囲内であれば、その組み合わせでもデコード可能です。例えば「06」は無効ですが「16」は有効です。
• 境界処理： i が 1 の場合（i-2 < 0）、dp[i-2] が存在しないため、代わりに 1 を加算しています。これは「最初の2文字だけで構成されるデコード」を表しています。

まとめ

このように、動的計画法を活用することで、一見複雑なデコード方法のカウント問題を線形時間で解くことができます。各位置において「1桁として読む場合」と「2桁として読む場合」の選択肢を累積していくのが核心的なアイデアです。フィボナッチ数列に似た漸化式の構造を持つことも覚えておくと良いでしょう。