
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
- 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.
- Recursive Function:
- Define a recursive function
rec(s)
that calculates the number of decodings for a substrings
. - Use a hash map (Map
or dictionary) to store results for previously computed substrings to avoid redundant calculations (memoization). - 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.
- Memoization: - Store the result of each substring in the hash map to ensure that each substring is only computed once.
- 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);
};