leetcode91

Posted on | In

91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: “12”
Output: 2
Explanation: It could be decoded as “AB” (1 2) or “L” (12).
Example 2:

Input: “226”
Output: 3
Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Idea

from 花花酱

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        self.cache = {"":1}
        return self.dp(s)

    def dp(self, s):
        # base case
        if s in self.cache:
            return self.cache[s]
        if s[0] == '0':
            return 0
        if len(s) == 1:
            return 1
        
        w = self.dp(s[1:])
        if int(s[:2]) <= 26:
            w += self.dp(s[2:])
        
        # cache 
        self.cache[s] = w
        return w