Is the time complexity same after memoization?
It’s O(N) after memoization. Each digit is decoded at most twice.
Could a test case ever begin with a zero? If a test case was ‘01’ would that be decodable into ‘a’, ‘0a’, neither?
// this solution is not following the template.
function decodeWays(digits) {
if(digits.length === 0) return 0;
return backtrack(digits, 0);
}
const backtrack = (digits, i) => { // 123
// found solution
if(i >= digits.length) return 1;
const firstDigit = Number.parseInt(digits.charAt(i));
if(firstDigit > 2) {
return backtrack(digits, i + 1);
}
if(i < digits.length - 1) {
const secondDigit = Number.parseInt(digits.charAt(i + 1));
if(secondDigit > 6) {
return backtrack(digits, i + 1);
} else {
return backtrack(digits, i + 1) + backtrack(digits, i + 2);
}
} else {
return backtrack(digits, i + 1);
}
}
Should have a test case for 127
Allows checking if algorithm excludes the 27 as being converted to a character A-Z ( which map to 1-26 respectively )
Didn’t use any mappings… just boundaries (0,27) … kinda cheating but passed on leet code where there are more test cases 
mp = {}
def decode_ways(digits: str, count = 0) → int:
if digits in mp:
return mp[digits]
if not digits:
return 1
if digits[0] == “0”:
return 0
c = decode_ways(digits[1:])
if len(digits) >=2:
if int(digits[:2]) > 26:
c += 0
else:
c += decode_ways(digits[2:])
mp[digits] = c
return mp[digits]
For the js memo solution, if (start_index in memo) return memo[i]; should be return memo[start_index] not i since i doesn’t exist. Same for const remaining = digits.slice(i); that’s being removed. I think it’d be really helpful if we could have a side by side comparison instead of all the changes being directly on top of each other in a single box. Makes it way easier to visualize imo.
Solution using iterative stack, no memo
int decode_ways(std::string digits) {
std::vectorstd::string prefixes(26);
for (int i = 1; i <= 26; ++i)
{
prefixes[i - 1] = std::to_string(i);
}
int num_ways = 0;
std::stack<std::string> dfs{};
dfs.push(digits);
while (not dfs.empty())
{
std::string the_rest = dfs.top(); dfs.pop();
if (the_rest.empty()) {
num_ways++;
continue;
}
else if (the_rest.front() == '0') {
continue;
}
for (int i = 0; i < 26; ++i)
{
std::string prefix = prefixes[i];
bool is_next = the_rest.find(prefix) == 0;
if (is_next)
{
dfs.push(the_rest.substr(prefix.size()));
}
}
}
return num_ways;
}
I think it’s O(N^2), because at each single or second digits, we have to do:
“remaining = digits[start_index:]”, which I think takes O(N) time.
exactly, thanks for saying this. Thought it was weird
def decode_ways(digits: str) → int:
# WRITE YOUR BRILLIANT CODE HERE
mapping = {num-64:chr(num) for num in range (65,91)}
path = []
ans = []
start_idx = 0
backtrack(digits, start_idx, mapping, path, ans)
print(ans)
return len(ans)
def backtrack(digits, start_idx, mapping, path, ans):
if start_idx > len(digits):
return
if start_idx == len(digits):
ans.append(''.join(path))
return
for length in range(1, 3):
current_num = digits[start_idx: start_idx+length]
current_chars = mapping[int(current_num)]
path.append(current_chars)
backtrack(digits, start_idx+length, mapping, path, ans)
path.pop()
Again, not following the backtracking template, as there is no pop(). I think you meant that the first part (identifying state) follows the one introduced in Backtracking section - which it does - but this is confusing. These problems are great, and your flow and structure are also awesome so far, but these sloppy little things with explanations undermine the quality.
In addition to backtracking, the solution is quite involved and crafty, it would really help if you lay out your thinking process and how you came up with it. Otherwise - it’s like watching magic, looks great but you know WTF is going on and feel this isn’t what you’ve paid for - just to watch others do it.
thanks for the feedback. we are updating backtracking section with new templates and better flow of problem selection. coming soon!
Structured Programming JS Solution:
const LETTERS = Array.from(Array(26).keys(), n => (n + 1).toString(10));
function decodeWays(digits, startIndex = 0, memo = {}) {
let result;
if (startIndex in memo) {
result = memo[startIndex];
} else if (startIndex === digits.length) {
result = 1;
} else {
let ways = 0;
const remaining = digits.slice(startIndex);
for (const letter of LETTERS) {
if (remaining.startsWith(letter)) {
ways += decodeWays(digits, startIndex + letter.length, memo);
}
}
memo[startIndex] = ways;
result = ways;
}
return result;
}
hey we added a new template for aggregation type problems and applied it to this problem. give it a look
How does my code look?
#_____________driver_______________#
def decode_ways(digits: str) -> int:
return helper(digits)
#_________helper____________#
def helper(digits, cache= {}):
if len(digits) == 0: return 1
if digits.startswith("0"): return 0
if digits not in cache:
ways = 0
# Given prefix of size 1 will always be valid, check suffix.
ways += helper(digits[1:], cache)
# Validate prefix of size 2. If valid check suffix.
prefix = digits[:2]
if 10 <= int(prefix) <= 26:
suffix = digits[2:]
ways += helper(suffix, cache)
cache[digits] = ways
return cache[digits]
My python code…
def decode_ways(digits: str) -> int:
if len(digits) == 0:
return 1
elif digits[0] == '0':
return 0
else:
answer = decode_ways(digits[1:])
if 10 <= int(digits[:2]) <= 26:
answer += decode_ways(digits[2:])
return answer