A message containing letters fromA-Zis 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.

Have you met this question in a real interview?

Yes

Example

Given encoded message12, it could be decoded asAB(1 2) orL(12).
The number of ways decoding12is 2.

class Solution:
    """
    @param s: a string,  encoded message
    @return: an integer, the number of ways decoding
    """

    #前i个元素总共有多少decode ways
    #dp[i] = dp[i - 1] | s[i - 1] != 0 在第i位元素不为0的情况下，前i位在用第i位元素单独decode的情况下总共有dp[i-1]种decode way
            #  +
            #  dp[i - 2] | s[i - 2] * 10 + s[i - 1] <= 26 and s[i - 2] != 0 在第i - 1位元素不为0且第i - 2 位和i - 1位元素组成的数字小于26的情况下，前i位在考虑后两位一起decode的情况下有dp[i - 2]种decode ways
    def numDecodings(self, s):
        # write your code here
        if not s or len(s) == 0:
            return 0

        dp = [0 for i in range(len(s) + 1)]
        dp[0] = 1

        for i in range(1, len(s) + 1):
            dp[i] = 0
            if s[i - 1] != '0':
                dp[i] = dp[i - 1]

            num = int(s[i - 2]) * 10 + int(s[i - 1])
            if i >= 2 and int(s[i - 2]) > 0 and num <= 26:
                dp[i] += dp[i - 2]
        print(dp)
        return dp[len(s)]