動機

有backtrack的味道，但因為要往前看一格就變成dp

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> 1'B' -> 2...'Z' -> 26

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, 11106 can be mapped into:

  • AAJF with the grouping (1 1 10 6)
  • KJF with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because 06 cannot be mapped into 'F' since 6 is different from 06.

Given a string s containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

 

Example 1:

Input: s = 12Output: 2Explanation: 12 could be decoded as AB (1 2) or L (12).

Example 2:

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

Example 3:

Input: s = 0Output: 0Explanation: There is no character that is mapped to a number starting with 0.The only valid mappings with 0 are 'J' -> 10 and 'T' -> 20, neither of which start with 0.Hence, there are no valid ways to decode this since all digits need to be mapped.

Example 4:

Input: s = 06Output: 0Explanation: 06 cannot be mapped to F because of the leading zero (6 is different from 06).

 

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

Sol

定義dfs(i)是以i為終點的組合數 但我們還需要一個狀態來看前面的數字有沒有被其他2位數用過

class Solution:
    def numDecodings(self, s: str) -> int:
        @cache
        def dfs(i,prev):
            if i >= len(s):
                return 1
            else:
                ret = dfs(i+1,True) if 1 <= int(s[i]) < 10 else 0
                if prev and i-1 >= 0 and 10 <= int(s[i-1:i+1]) <= 26:
                    ret += dfs(i+1,False)
                return ret
        return dfs(0,False)