Dare2Solve
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.
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.
Base Cases:
Recursive Function:
rec(s)
that calculates the number of decodings for a substring s
.Map
or dictionary) to store results for previously computed substrings to avoid redundant calculations (memoization).Explore Decoding Options:
Memoization:
Return Result: The function numDecodings
returns the result of decoding the entire string by invoking the recursive function on the input string.
(O(n)), where (n) is the length of the string. Each substring is processed at most once due to memoization.
(O(n)) for the hash map that stores the intermediate results for each substring.
class Solution {
public:
std::unordered_map<std::string, int> 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;
}
};
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
class Solution {
private Map<String, Integer> 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;
}
}
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);
};