Decode Ways

Question

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.

Tags

• String
• Dynamic programming

Thought

This problem is very similar to the problem Climbing Stairs. We need to determine whether split the string to obtain one-digit number or two-digit number and use the DP table to store them. However, there are more corner cases comparing to the Climbing Stairs problem.

Code

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == '' or s[0] == '0':
            return 0
        dp = [1, 1]
        for i in xrange(2, len(s) + 1):
            num = s[i-2:i]
            if '10' <= num <= '26' and s[i-1] != '0':
                dp.append(dp[i-2] + dp[i-1])
            elif num == '10' or num == '20':
                dp.append(dp[i-2])
            elif s[i-1] != '0':
                dp.append(dp[i-1])
            else:
                return 0
        return dp[-1]