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

https://algo.monster/problems/decode_ways

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 :slight_smile:

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 :slight_smile:

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)