Leetcode 91: Decode Ways

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

Code

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or s.startswith('0'):
            return 0
            
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        dp[1] = 1

        for i in xrange(1, len(s)):
            if 1 <= int(s[i]) <= 9:
                dp[i+1] += dp[i]
            if 10 <= int(s[i-1:i+1]) <= 26:
                dp[i+1] += dp[i-1]

        return dp[-1]

Idea

Use 1D DP. dp[0] means an empty string will have one way to decode, dp[1]means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.

Reference: https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation

I was initially trying the following code. However this easily time limits when the input string is long:

class Solution(object):
    def __init__(self):
        self.res = 0

    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        self.helper(s)
        return self.res
    
    def helper(self, s):
        if s.startswith('0'):
            return
        
        if len(s) == 1:
            self.res += 1
        elif len(s) == 2:
            if int(s) <= 26:
                self.res+= 1
            self.helper(s[1:])
        else:
             self.helper(s[1:]) 
             if int(s[:2]) <= 26:
                 self.helper(s[2:])