Pythonでエンコードされたメッセージのデコード方法の総数を求めるプログラム

問題の概要

「a」= 1、「b」= 2、…「z」= 26 というアルファベットと数字の対応関係があるとします。このとき、エンコードされたメッセージ(数字列)が与えられれば、そのメッセージをデコードできる方法が何通りあるかを数えるのが本記事のテーマです。

例えば、入力が message = "222" の場合、出力は 3 になります。これは次の3通りにデコードできるためです。

• b・b・b(2, 2, 2)
• b・v(2, 22)
• v・b(22, 2)

解決のアプローチ:動的計画法(DP)

この問題は動的計画法を用いることで効率的に解くことができます。各位置 i までの文字列についてデコード方法の総数を記録し、1文字または2文字ずつ区切る場合分けを行います。具体的な手順は以下の通りです。

• memo := メッセージの長さ + 1 のサイズを持つ、すべて 0 のリストを作成する
• memo[0] := 1(空文字列のデコード方法は1通り)
• memo[1] := message[0] が "0" でなければ 1、そうでなければ 0
• i を 2 からメッセージの長さまで以下を繰り返す:
  • n1 := message[i-1:i](直前の1桁)の数値
  • n2 := message[i-2:i](直前の2桁)の数値
  • n1_valid := n1 > 0 のとき有効
  • n2_valid := n2 > 9 かつ n2 < 27 のとき有効(10〜26のみ2桁として成立)
  • n1_valid が真ならば、memo[i] += memo[i-1]
  • n2_valid が真ならば、memo[i] += memo[i-2]
• 最後に memo の末尾の要素を返す

先頭が "0" の場合は単独ではデコードできず、また2桁の数値は 10 以上 26 以下でなければならない点がポイントです。

実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def solve(self, message):
      memo = [0 for i in range(len(message)+1)]
      memo[0] = 1
      memo[1] = 1 if message[0]!="0" else 0

      for i in range(2,len(message)+1):
         n1 = int(message[i-1:i])
         n2 = int(message[i-2:i])

         n1_valid= n1>0
         n2_valid= n2>9 and n2<27

         if n1_valid:
            memo[i]+=memo[i-1]
         if n2_valid:
            memo[i]+=memo[i-2]
      return memo[-1]
ob = Solution()
message = "2223"
print(ob.solve(message))

入力

"2223"

出力

5

結果の解説

入力 "2223" の場合、出力は 5 となります。これは以下の5通りのデコードが可能であることを意味します。

• b・b・b・c(2, 2, 2, 3)
• v・b・c(22, 2, 3)
• b・v・c(2, 22, 3)
• b・b・w(2, 2, 23)
• v・w(22, 23)

このアルゴリズムの計算量は O(n)、必要なメモリも O(n) であり、非常に効率的です。memo 配列を使わず直前の2つの値だけを保持すれば、空間計算量を O(1) に抑えることもできます。