Python 中的解码方法

pythonserver side programmingprogramming更新于 2025/10/25 21:00:17

假设我们有一条包含从 A 到 Z 的字母的消息，使用以下映射将其编码为数字 − 'A' → 1, 'B' → 2 ... 'Z' → 26。因此，如果我们有一个非空字符串，仅包含数字，那么我们必须找出有多少种可以解码的方法。因此，如果字符串类似于"12"，则可以由"AB"或"L"组成，因此有两种可能的方法。所以答案是 2。

为了解决这个问题，我们将遵循以下步骤 −

我们将使用动态规划来解决这个问题。
n := s 的长度
dp := 一个包含 n 个 0 的数组
如果 s[0] 不是 ‘0’，则 dp[0] := 1
对于范围从 1 到 n – 1 的 i
- x := s[i] 作为整数，y := s 的子字符串从索引 i – 1 到 i + 1 作为整数
- 如果 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"))