91. Decode Ways

Description

The numDecodings function determines the number of ways to decode a string of digits, where each digit or pair of digits can represent a letter ('1' -> 'A', '2' -> 'B', ..., '26' -> 'Z'). The input string may contain digits from '0' to '9', and the goal is to find all possible ways to interpret the string as a sequence of characters.

Intuition

To solve the problem, we use dynamic programming with memoization. Each digit in the string can be decoded in different ways depending on its value and the values of adjacent digits. By recursively exploring all possible interpretations while storing intermediate results, we can efficiently calculate the total number of valid decodings.

Approach

1. Base Cases: - If the string is empty, there's one way to decode it (an empty sequence). - If the string starts with '0', it cannot be decoded, so return 0. - If the string has one digit, return 1 because a single digit can only be decoded in one way.
2. Recursive Function: - Define a recursive function rec(s) that calculates the number of decodings for a substring s. - Use a hash map (Map or dictionary) to store results for previously computed substrings to avoid redundant calculations (memoization).
3. Explore Decoding Options: - Single Digit: Always consider the first digit and recursively decode the rest of the string. - Two Digits: If the first two digits form a number between 10 and 26, consider this as one valid decoding and recursively decode the remaining string after these two digits.
4. Memoization: - Store the result of each substring in the hash map to ensure that each substring is only computed once.
5. Return Result: The function numDecodings returns the result of decoding the entire string by invoking the recursive function on the input string.

Complexity

Time Complexity:

(O(n)), where (n) is the length of the string. Each substring is processed at most once due to memoization.

Space Complexity:

(O(n)) for the hash map that stores the intermediate results for each substring.

Code

C++

class Solution {
public:
    std::unordered_map hash;

    int numDecodings(std::string s) {
        return rec(s);
    }

private:
    int rec(const std::string& s) {
        if (hash.find(s) != hash.end()) return hash[s];
        if (s[0] == '0') return 0;
        if (s.length() == 1) return 1;
        if (s.length() == 0) return 1;

        int res = rec(s.substr(1));

        if (std::stoi(s.substr(0, 2)) <= 26) {
            res += rec(s.substr(2));
        }

        hash[s] = res;
        return res;
    }
};

Python

class Solution:
    def __init__(self):
        self.hash = {}

    def numDecodings(self, s: str) -> int:
        return self.rec(s)

    def rec(self, s: str) -> int:
        if s in self.hash:
            return self.hash[s]
        if s.startswith('0'):
            return 0
        if len(s) == 1:
            return 1
        if len(s) == 0:
            return 1

        res = self.rec(s[1:])

        if int(s[:2]) <= 26:
            res += self.rec(s[2:])

        self.hash[s] = res
        return res

Java

class Solution {
    private Map hash;

    public Solution() {
        this.hash = new HashMap<>();
    }

    public int numDecodings(String s) {
        return rec(s);
    }

    private int rec(String s) {
        if (hash.containsKey(s)) {
            return hash.get(s);
        }
        if (s.startsWith("0")) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        if (s.length() == 0) {
            return 1;
        }

        int res = rec(s.substring(1));

        if (Integer.parseInt(s.substring(0, 2)) <= 26) {
            res += rec(s.substring(2));
        }

        hash.put(s, res);
        return res;
    }
}

JavaScript

var numDecodings = function(s) {

    const hash = new Map();
    function rec(s) {

        if(hash.has(s)) return hash.get(s);
        if(s[0] === '0') return 0;
        if(s.length === 1) return 1; 
        if(s.length === 0) return 1;

        console.log(s.substring(1), '---> ', rec(s.substring(1)));
        console.log(s.substring(2), '---> ', rec(s.substring(2)));

        let res =  rec(s.substring(1));

        if(parseInt(s.substring(0,2)) <= 26) {
             res += rec(s.substring(2));   
        }
        hash.set(s, res);
        console.log('result', res);

        return res; 
    }
    return rec(s);

};