91.-decode-ways.md

91. Decode Ways

• Medium

• 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 test cases are generated so that the answer fits in a 32-bit integer.

Analysis

This is problem that can be solved by recursion. Since the coding only goes from "1" to "26", for each sequence there is only two choices each step: cut 1 or cut 2. Then the sum of those choices will be the value of this sequence. And now you can see how the recursion works.

There are a few limitations, first, if "0" is the start of the current sequence, then the value of current sequnce is 0. Because "06" is not equal to "6" and "0" itself doen't match any letter.

Second, if the result of cutting two digits is a value larger than 26. For example, 27. Then we know that it is not going to work that way and we can only chose to cut 1 digit.

class Solution:
    def numDecodings(self, s: str) -> int:
        seen={}
        return self.helper(s,0,seen)
        
    def helper(self,s,k,seen):
        if k==len(s):
            seen[k]=1
            return 1
        if s[k]=="0":
            seen[k]=0
            return 0
        if k in seen:
            return seen[k]
        
        if k<len(s)-1:
            if int(s[k:k+2])<=26:
                ans=self.helper(s,k+2,seen)+self.helper(s,k+1,seen)
                seen[k]=ans
                return ans
        ans=self.helper(s,k+1,seen)
        seen[k]=ans
        return ans