Python解碼訊息方法計數程式

假設我們有這樣的對映：'a' = 1, 'b' = 2, ... 'z' = 26，並且我們有一個編碼的訊息字串，我們需要計算它可以解碼的方案數。

例如，如果輸入訊息為 "222"，則輸出為 3，因為它可以有 3 種解碼方式：bbb，bv 和 vb。

為了解決這個問題，我們將遵循以下步驟：

  • memo := 一個大小與訊息大小相同的 0 列表 + 1

  • memo[0] := 1

  • 當message[0]不等於"0"時，memo[1] := 1；否則為 0

  • 對於範圍從 2 到訊息大小的 i，執行：

    • n1 := message[從索引 i-1 到 i] 的數值

    • n2 := message[從索引 i-2 到 i] 的數值

    • n1_valid:= 當 n1 > 0 時為真

    • n2_valid:= 當 n2 > 9 且 n2 < 27 時為真

    • 如果 n1_valid 為真，則

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

    • 如果 n2_valid 為真，則

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

  • 返回 memo 的最後一個元素

讓我們看看下面的實現來更好地理解：

示例

即時演示

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

更新於：2020年10月7日

313 次檢視

啟動您的職業生涯

透過完成課程獲得認證

開始學習
廣告