Pythonでウェイをデコードする

AからZまでの文字を含むメッセージが、次のマッピングを使用して数字にエンコードされているとします-'A'→1、'B'→2...'Z'→ 26.したがって、数字のみを含む空でない文字列が1つある場合、デコードできる方法がいくつあるかを見つける必要があります。したがって、文字列が「12」のような場合、それは「AB」または「L」から作成できるため、2つの方法が考えられます。したがって、答えは2になります。

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

• 動的計画法を使用してこれを解決します。
• n：=sの長さ
• dp：=0の数がnの配列
• s [0]が「0」でない場合、dp [0]：=1
• 1からn–1の範囲のiの場合
  • x：=s [i]は整数、y：=インデックスi –1からi+1までのsの部分文字列
  • x>=1かつy<=9の場合、dp [i]：=dp [i] + dp [i – 1]
  • y>=10かつy<=26
    の場合
    • i – 2> =0の場合、dp [i]：=dp [i] + dp [i – 2]、それ以外の場合はdp[i]を1増やします
• dpの最後の要素を返す

例（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