本文共 1694 字，大约阅读时间需要 5 分钟。

题目描述： A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

分析：采用动态规划方法，定义一个数组dp，大小为：数组大小+1，令dp[0]=1,其他的数组元素初值设为0，dp[i]表示数字字符串的前i位（包含第i位）有多少种解码方案。

遍历数字字符串s， 如果当前位s[i]不为0，并且当前位可以和前面1位能够组成闭区间 [11,26] 之间的某个数（即：当前位和其前一位是某个字母的编码），那么dp[i+1]=dp[i]+dp[i-1]; 如果当前位s[i]不为0，并且当前位和其前面的一位构成的数字不在区间[11,26]内（即：当前位和其前一位不是某个字母的编码），那么dp[i+1]=dp[i]; 如果当前位s[i]为0，则其前一位一定存在并且一定是1或2（因为该数字字符串是某一字母串的编码，而只有10和20是字母的编码），又因为单独一个0不是任何字母的编码，那么在这种情况下，dp[i+1]=dp[i-1] 【第一位肯定不能为0，也不能有连续的0 像10，20这种，有dp[i] = dp[i-2] 00,30,40...等都是非法的。。。。】

python代码1:

class Solution(object):    def numDecodings(self, s):        """        :type s: str        :rtype: int        """        if len(s)==0:            return 0        dp=[1]+[0]*len(s)        bool_ok=lambda x:x[0]!='0' and int(x)>=1 and int(x)<=26        for i in range(1,len(s)+1):            dp[i]=dp[i-1] if bool_ok(s[i-1:i]) else 0            if i>=2:                dp[i]=dp[i]+(dp[i-2] if bool_ok(s[i-2:i]) else 0)        return dp[len(s)]

python代码2:

class Solution(object):    def numDecodings(self, s):        """        :type s: str        :rtype: int        """        if s=='':            return 0        dp=[1]+[0]*len(s)        bool_ok=lambda x:x[0]!='0' and int(x)>=1 and int(x)<=26        for i in range(len(s)):            dp[i+1]=dp[i] if bool_ok(s[i:i+1]) else 0            if i>=1:                dp[i+1]+=dp[i-1] if bool_ok(s[i-1:i+1]) else 0        return dp[len(s)]

转载地址：http://wcyai.baihongyu.com/