LC19. Remove Nth Node From End of List

# time O(N) space O(N)
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0]*(n+1)
        # case 1  not 0 
        # case 2   0 
        # dp[i] += dp[i-1]  || += dp[i-2] , dp[i]: there are dp[i] case to decode for string s[:i]
        dp[0] = 1 # special case to ensure dp[2] is valid 
        dp[1] = 1 if s[0] != '0' else 0 # start base case dp[1], dp[2]
        for i in range(2,n+1):
            first = s[i-1:i]
            second = s[i-2:i]
            if 1 <= int(first) <= 9:
                dp[i] += dp[i-1]
            if 10 <= int(second) <= 26:
                dp[i] += dp[i-2] 
        return dp[n]

# memoization

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        memo = [None]*n
        def helper(pos,s,mem):
            n = len(s)
            if pos == n:
                return 1
            if s[pos] == '0':
                return 0
            if mem[pos] != None:
                return mem[pos]
            # decode with 1 digit 
            res = helper(pos+1,s,mem)
            # decode with 2 digits 
            if pos < n-1 and ( s[pos] =='1' or (s[pos] == '2' and s[pos+1] < '7')):
                res += helper(pos+2,s,mem)
            mem[pos] = res
            return mem[pos]
        return helper(0,s,memo)