Python中的解码方式
假设我们有一条消息，使用以下映射将包含从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–2>=0，则dp[i]：=dp[i]+dp[i–2]，否则将dp[i]增加1
x：=s[i]为整数，y：=s的子串，从索引i–1到i+1为整数
如果x>=1且y<=9，则dp[i]：=dp[i]+dp[i–1]
如果y>=10且y<=26
返回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