Topic analysis:

A message containing the letters A-Z is encoded as follows: 'a' - > 1, B '- > 2 ，‘Z’ -> 26. Given a non empty string containing only numbers, calculate the total number of decoding methods. Such as:
Input: "12"
Output: 2
Explanation: it can be decoded as "AB" (12) or "L" (12).

Solutions:

This problem can be solved by decomposing it into several small problems, generally involving several cases of string finding, or the optimal situation can be used for dynamic programming. In fact, there are only four situations:

1. If there is a non-zero number after the beginning of 1 or 2, the result is to remove all cases of the previous character + all cases of the last two characters
2. Starting with 1 or 2 and followed by 0, the result is to remove all cases of the last two characters
3. If the current number is not 0, the result is to remove all the previous characters
4. If 0 appears continuously, it cannot be decoded and 0 is returned.

The code is

            if (s[i - 2: i ] > '10' and s[i - 2: i] <= '26') and s[i - 1] != '0':
                dp.append(dp[i - 1] + dp[i - 2])
            elif s[i - 2: i] == '10' or s[i - 2: i] == '20':
                dp.append(dp[i - 2])
            elif s[i - 1] != '0':
                dp.append(dp[i - 1])
            else:
                return 0

Test code: (Runtime: 40 ms, foster than 94.21%)

class Solution:
    def numDecodings(self, s):
        if s[0] == '0': return 0
        dp=[1,1]
        for i in range(2, len(s) + 1):
            if (s[i - 2: i ] > '10' and s[i - 2: i] <= '26') and s[i - 1] != '0':
                dp.append(dp[i - 1] + dp[i - 2])
            elif s[i - 2: i] == '10' or s[i - 2: i] == '20':
                dp.append(dp[i - 2])
            elif s[i - 1] != '0':
                dp.append(dp[i - 1])
            else:
                return 0
        return dp[len(s)]

print(Solution().numDecodings("12"))    #Please delete this line when submitting

Reference blog

Appendix: the recursion I used at the beginning of this problem can also be solved, but TLE, with recursion code

class Solution:
    def numDecodings(self, s: str) -> int:
        self.n = 0
        def dfs(s):
            if s == '':
                self.n += 1
            elif (s[0] == '1') and 1 < len(s) or (s[0] == '2' and 1 < len(s) and s[1] <= '6'):
                dfs(s[1:])
                dfs(s[2:])
            elif s[0] == '0':
                return
            else:
                dfs(s[1:])
        dfs(s)
        return self.n

print(Solution().numDecodings("12"))    #Please delete this line when submitting