Description:

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).

Solutions:

Solution1: brute force DFS

TLE at "9371597631128776948387197132267188677349946742344217846154932859125134924241649584251978418763151253"

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s:
            return 0
        
        seq_ls = []
        count = 0
        def dfs(seq):
            nonlocal count
            nonlocal seq_ls
            
            if seq == len(s):
                # print(seq_ls)
                count += 1 
            elif seq == len(s)-1:
                if s[seq] != "0":
                    # print(seq_ls+[seq])
                    count += 1  
            elif seq < len(s)-1:
                if s[seq] != "0":
                    seq_ls.append(seq)
                    dfs(seq+1)
                    seq_ls.pop()
                    # print("+2:",int(s[seq:seq+2]))
                    if int(s[seq:seq+2]) < 27 and int(s[seq:seq+2]) > 0:
                        seq_ls.append(seq)
                        dfs(seq+2)
                        seq_ls.pop()
        
        dfs(0)
        return count

Solution2: hash table递归

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s:
            return 0
        
        dic = {}
        def dfs(seq):
            if seq in dic:
                return dic[seq]
            
            if seq == len(s): # last two is okay
                return 1
            elif seq == len(s)-1 and s[seq] != "0": # last one should not be "0"
                return 1
            elif seq < len(s)-1 and s[seq] != "0": # before the last one, the first should not be "0"
                dic[seq] = dfs(seq+1) # move 1 step
                if int(s[seq:seq+2]) < 27 and int(s[seq:seq+2]) > 0: # move 2 steps
                    dic[seq] += dfs(seq+2)
                return dic[seq]
            else:
                return 0
        return dfs(0)

Runtime: 36 ms, faster than 85.82% of Python3 online submissions for Decode Ways.
Memory Usage: 14.4 MB, less than 12.55% of Python3 online submissions for Decode Ways.

sample 20 ms submission: 递推(实际上在测试集上并不比递归更快，估计len(s)没有太大)

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or len(s) == 0:
            return 0
        # dp[i]: the number of decode ways ending at index i
        dp = [0] * (len(s) + 1)
        dp[0] = 1 # empty
        dp[1] = 1 if s[0] != "0" else 0 # s[0:1]
        for i in range(2, len(s) + 1):
            prev1 = s[i - 1: i]
            prev2 = s[i - 2: i]
            if 1 <= int(prev1) <= 9: # easy to understand
                dp[i] += dp[i - 1]
            if 10 <= int(prev2) <= 26: 
# if using 0 < int(prev2) < 27, OJ will report an wrong answer when input == "01"
                dp[i] += dp[i - 2]

        return dp[-1]