LC 91 - Decode Ways

Question

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12"
Output: 2

Explanation:

“12” could be decoded as “AB” (1 2) or “L” (12).

Example 2:

Input: s = "226"
Output: 3

Explanation:

“226” could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Example 3:

Input: s = "06"
Output: 0

Explanation:

“06” cannot be mapped to “F” because of the leading zero (“6” is different from “06”). In this case, the string is not a valid encoding, so return 0.

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Links

Question here and solution here

Solution

concept

top down: memoization

This is the recursive solution where we cache the intermedia results. The key idea is to track if we can proceed i + 1 or i + 2 depend on the conditions and sum these possibilities at each index and cache it for later usage.

bottom up

This is very similar to the memoization solution in terms of logic. We will iterate the string in reverse directions (i.e. solve sub problems).

code

class Solution:
	"""
	top down: memoization
	"""
    def dfs(self, i, s):
        """
        i means string start from i -> eos, to find how many ways of decode can be found for this substring
        """
        # if this index already solved -> obtained num of ways of decode
        # or we reached (beyond) end of str
        if i in self.dp:
            return self.dp[i]
        # if char is 0, then it is not possible to decode
        if s[i] == "0":
            return 0

        # go for next char
        result = self.dfs(i + 1, s)
        # if i + 1 never out of bound and curr one is either 1 or 2 (2 must also satsify the next char is in 0-6)
        if i + 1 < len(s) and (s[i] == "1" or (s[i] == "2" and s[i+1] in "0123456")):
            # num of ways from the previous one is being added tgt
            result += self.dfs(i + 2, s)
        # update the cache, this is the dp part
        self.dp[i] = result
        return result

    def numDecodings(self, s: str) -> int:
        """
        dp (recursive) approach

        time complexity O(n)
        space complexity O(n)

        note the way dfs works is to process the str backwards (i.e. s[-1] first)
        """
        # dp cache to store num of decode ways at each index
        # this is the base case where if our step reach beyond the len of s
        # then it return 1 (way of decoding)
        # also edge case for empty s
        self.dp = {len(s): 1}

        # start at index 0
        result = self.dfs(0, s)
        return result
        
class Solution:
	"""
	top-down: memoization
	"""
    def numDecodings(self, s: str) -> int:
        cache = {}
        def dfs(i):
            if i in cache:
                return cache[i]
            if i == len(s):
                return 1
            if i > len(s) or s[i] == "0":
                return 0

            cache[i] = dfs(i + 1)
            if s[i] == "1" or (i+1 < len(s) and s[i] == "2" and s[i+1] in "0123456"):
                cache[i] += dfs(i + 2)
            return cache[i]

        return dfs(0)
        

class NeetSolution:
    """
	bottom up solution

    time complexity O(n)
    space complexity O(1)
    """
    def numDecodings(self, s: str) -> int:
        # edge case for empty s
        # also base case for dp
        dp = {len(s): 1}
        # loop backwards -> start from last char
        for i in range(len(s) - 1, -1, -1):
            # if char is 0, then it is not possible to decode
            if s[i] == "0":
                dp[i] = 0
            # if curr char is 1->9, then it is possible to decode
            # we put the previous solved index (i+1 since we are going backwards) into the current index first
            else:
                dp[i] = dp[i + 1]
            # same condition as the recursive approach
            if i + 1 < len(s) and (s[i] == "1" or s[i] == "2" and s[i + 1] in "0123456"):
                # same pos we add on the previous solved index (i+2 since we are going backwards)
                dp[i] += dp[i + 2]
        return dp[0]
        
class Solution:
	"""
	bottom up solution
	"""
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[-1] = 1

        for i in range(len(dp)-2, -1, -1):
            if s[i] == "0":
                dp[i] = 0
            else:
                dp[i] = dp[i + 1]
            
            if i + 1 < len(s) and (s[i] == "1" or s[i] == "2" and s[i + 1] in "0123456"):
                dp[i] += dp[i + 2]
        
        return dp[0]

Complexity

time: $O(n)$
space: $O(n)$