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 次查看

启动您的职业生涯

通过完成课程获得认证

开始学习
广告