# Num Ways to Decode a Message - Backtracking / Aggregation and Memoization

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:
if 10 <= int(digits[:2]) <= 26:
``````

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)

``````