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
I realized that I donāt need to create the mapping afterwards
def decode_ways(digits: str) -> int:
mapping = {
str(i + 1): chr(ord("A") + i) for i in range(27)
}
length = len(digits)
dp = [0] * (length) + [1]
for i in reversed(range(length)):
for j in range(1, 3):
if i + j > length:
continue
if digits[i:i+j] not in mapping:
continue
dp[i] += dp[i + j]
return dp[0]
def decode_ways(digits: str) -> int:
mapping = {
str(i + 1): chr(ord("A") + i) for i in range(27)
}
length = len(digits)
def dfs(idx, mem={}):
if idx >= length:
return 1
if idx in mem:
return mem[idx]
ans = 0
for i in range(1, 3):
if idx + i > length:
continue
if digits[idx:idx+i] not in mapping:
continue
ans += dfs(idx + i)
mem[idx] = ans
return ans
return dfs(0)
O(n) time complexity
O(1) space complexity
def is_valid(s):
if s[0] == "0":
return False
if len(s) == 2:
if int(s[1]) > 6:
return False
if s[0] not in "12":
return False
return True
def decode_ways(digits: str) -> int:
length = len(digits)
def dfs(idx, mem={length: 1}):
if idx in mem:
if idx + 1 in mem:
del mem[idx + 1] # O(1) memory
return mem[idx]
ans = 0
for i in range(1, 3):
if idx + i > length:
continue
if not is_valid(digits[idx:idx+i]):
continue
ans += dfs(idx + i)
mem[idx] = ans
return ans
return dfs(0)