leetcode：91. Decoding method [DFS + memorization]

analysis

dfs（s) Express this s How many different solutions can be generated
First, if it's empty , It must be a solution
A leading 0 unsolvable
There is only one （ Non leading 0） A solution
then res Record answer
First plus dfs(s[1:]) First position ok
Then judge s[:2] Is it legal , If so, you can continue to add dfs(s[2:])

ac code

class Solution:
    def numDecodings(self, s: str) -> int:
        # dfs +  Memorize 

        #  The top-down 
        @cache
        def dfs(s):
            if not s:
                return 1
            
            if s[0] == '0':
                return 0
            
            if len(s) == 1:
                return 1
            
            res = 0
            res += dfs(s[1:])

            if int(s[:2]) <= 26:
                res += dfs(s[2:])
            
            return res
        
        return dfs(s)

summary

dfs + Memorize Indiscriminate killing