educative.io

Solution missing memoization

Courses
,
#1

I believe the solution is missing a key part of memoization:

function dfs(digits, i, memo) {
    if (i === digits.length) return 1;

//the below line is missing:
    if (i in memo) return memo[i];

    let ways = 0;
    const remaining = digits.slice(i);
    for (const letter of LETTERS) {
        if (remaining.startsWith(letter)) {
            // add number of ways returned from child node
            ways += dfs(digits, i + letter.length, memo);
        }
    }
    memo[i] = ways
    return ways;
}

The tests still pass without it because the test inputs aren’t that large, but I noticed that the memo wasn’t actually doing anything and that we were missing: if (i in memo) return memo[i];

Course: The Algorithms and Data Structures Interview Crash Course - Learn Interactively
Lesson: Decode String - The Algorithms and Data Structures Interview Crash Course