Pythonでメッセージをデコードできるいくつかの方法を見つけるためのプログラム

'a' =1、'b' =2、...'z' =26のようなマッピングがあり、エンコードされたメッセージメッセージ文字列があるとすると、デコードできる方法の数を数える必要があります。

したがって、入力がmessage ="222"の場合、出力は3になります。これは、bbb、bv、vbの3つの方法でデコードできるためです。

これを解決するには、次の手順に従います-

• memo：=メッセージサイズ+1と同じサイズの0のリスト

• memo [0]：=1

• memo [1]：=1（message [0]が「0」と同じでない場合）それ以外の場合は0

• 2からメッセージのサイズまでの範囲のiの場合、実行します

  • n1：=メッセージの数値[インデックスi-1からiまで]

  • n2：=メッセージの数値[インデックスi-2からiまで]

  • n1_valid：=n1> 0

    の場合はtrue

  • n2_valid：=n2>9およびn2<27の場合はtrue

  • n1_validがtrueの場合、

    • memo [i]：=memo [i] + memo [i-1]

  • n2_validがtrueの場合、

    • memo [i]：=memo [i] + memo [i-2]

• メモの最後の要素を返す

理解を深めるために、次の実装を見てみましょう-

例

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