Leetcode: Decode ways

Characters can be encoded via different numbers. A -> 1, B -> 2, ..., Z -> 26. Given a string s of numbers, return the number of possible decodings. For example 12 can be decoded as A,B and as L. We can look at this problem as a recursive problem. By checking the first two characters of each string, we can see if we decode it in zero, one or two ways. It is impossible to decode a string if it starts in 0, according to the rules. In this case we can return immediately and do not need to proceed further. Next, we test if the string is at least 2 long. If this is the case we can either decode it as a single character or as two characters. The exception for two characters is that the number has to be below or equal to 26. Lastly, it is a good idea to add memoization to the algorithm and avoid performing the same operation twice. For example if we have a string of length 4: 1-1-1-1, we can decode it as 11-... or as 1-1.... However, the number of ways the remainder can be decoded stays the same.

class Solution:
  def numDecodings(self, s: str) -> int:
    mem = {}
    def inner(s):
      if s in mem:
        return mem[s]

      if s == "":
        return 1
      
      if s[0] == '0':
        return 0
      
      if len(s) >= 2 and s[:2] <= '26':
        mem[s] = inner(s[1:]) + inner(s[2:])
        return mem[s]
      else:
        mem[s] = inner(s[1:])
        return mem[s]

    return inner(s)

if __name__ == '__main__':
  s = Solution().numDecodings
  
  print(s('11106'), 2)
  print(s('06'), 0)
  print(s('12'), 2)
  print(s('226'), 3)
  print(s("2611055971756562"), 4)

Runtime: 74 ms, faster than 8.01% of Python3 online submissions for Decode Ways. Memory Usage: 14.3 MB, less than 6.92% of Python3 online submissions for Decode Ways.