Decode Ways

https://leetcode.com/problems/decode-ways/

Approach 1: Recursive with Memoization

Either decode one digit, or decode 2 digits. The decisions make up a tree. Use memoization to reuse results from sub problems.

@lru_cache(maxsize=None)
def recursiveWithMemo(index, s) -> int:
    # If you reach the end of the string
    # Return 1 for success.
    if index == len(s):
        return 1
 
    # If the string starts with a zero, it can't be decoded
    if s[index] == "0":
        return 0
 
    if index == len(s) - 1:
        return 1
 
    answer = self.recursiveWithMemo(index + 1, s)
    if int(s[index:index + 2]) <= 26:
        answer += recursiveWithMemo(index + 2, s)
 
    return answer
 
def numDecodings(s: str) -> int:
    return recursiveWithMemo(0, s)

Time and space complexity: $O(n)$

Approach 2: Iterative/DP

Similar to the idea in house-robber, but goes from start to end.

n = len(s)
# Array to store the subproblem results
dp = [0 for _ in range(n + 1)]
 
dp[0] = 1  # Base case is the key
# Ways to decode a string of size 1 is 1. Unless the string is '0'.
# '0' doesn't have a single digit decode.
dp[1] = 0 if s[0] == "0" else 1
 
for i in range(2, n):
 
    # Check if successful single digit decode is possible.
    if s[i - 1] != "0":
        dp[i] = dp[i - 1]
 
    # Check if successful two digit decode is possible.
    two_digit = int(s[i - 2: i])
    if 10 <= two_digit <= 26:
        dp[i] += dp[i - 2]
 
return dp[-1]

Time and space: $O(n)$

Approach 3: Optimized DP

if s[0] == "0":
    return 0
 
two_back = 1
one_back = 1
for i in range(1, len(s)):
    if not (one_back or two_back):
        # neither single digit nor double digit decoding worked before
        return 0
    current = 0
    if s[i] != "0":  # can do single digit
        current = one_back
    two_digit = int(s[i - 1:i + 1])
    if 10 <= two_digit <= 26:
        current += two_back  # can also do two digits
    two_back = one_back
    one_back = current
 
return one_back  # the last current