Open the lock - LeetCode, why counter keeps incrementing in every recursive call?

user_9764089 0
Viewed 104

I am working on the Open the lock challenge on LeetCode:

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1

Input: deadends = ["0201","0101","0102","1212","2002"], 
       target = "0202"
Output: 6

This is my attempt:

var openLock = function(deadends, target) {
    let res = 0;
    let seen = []
    let recursion = function(temp,counter=0){
        if(deadends.includes(temp) || seen.includes(temp)) return
        seen.push(temp)
        if(temp ===target){
            res = counter
            return
        }
        for(let i=0; i<temp.length; i++){
            let s1 = temp.substring(0, i) + (+temp[i]+1)%10 + temp.substring(i + 1)
            let s2 = temp.substring(0, i) + (+temp[i]+9)%10 + temp.substring(i + 1)
            recursion(s1,counter+1)
            erecursion(s2,counter+1)
        }
    }
    recursion('0000')
    return res ?? -1;
};

My output for the example here is 2230, and I don't understand why. It's as if the counter variable value gets updated in every recursive call.

greedy breadth-first-search sorting algorithm javascript
1 Answers

This happens because your code marks every visited combination as "seen" without making sure that you reached that combination via the shortest path, and so your code will never ever try to reach that same combination with a shorter path.

For the example input, your code will visit combinations in the following order:

0000
1000
2000
...
9000
0100
1100
2100
...
9100
0200
1200
...
...

...all this happens without backtracking! As your for loop will always find some possibilities that have not yet been visited, the recursion just deepens, and deepens.

...and eventually it will hit the target combination, but via a very long and deep recursion path. Then that combination is marked as seen and so your code will never consider shorter paths that could have lead to the same solution.

Depth first versus Breadth first

Although you could make it work with a depth-first search, it is somewhat easier to solve this with a breadth-first search, as that is more suitable for finding shortest paths. With a depth-first search you should only mark as "seen" the combinations that are on the current path. So when backtracking out of recursion, those deeper nodes should be unmarked.

Here is a breadth-first solution:

var openLock = function(deadends, target) {
    if (target == "0000") return 0; // boundary case
    let seen = new Set(deadends);
    if (seen.has("0000")) return -1; // boundary case
    let frontier = ["0000"];
    let res = 1;
    while (frontier.length) {
        let nextFrontier = [];
        for (let combi of frontier) {
            for (let dial = 0; dial < 4; dial++) {
                for (let add = 1; add < 10; add += 8) {
                    let neighbor = combi.slice(0, dial) + 
                                   (+combi[dial] + add) % 10 +
                                   combi.slice(dial+1);
                    if (!seen.has(neighbor)) {
                        if (neighbor == target) return res;
                        nextFrontier.push(neighbor);
                        seen.add(neighbor);
                    }
                }
            }
        }
        frontier = nextFrontier;
        res++;
    }
    return -1;    
};

This solution could be further optimised. For instance, the add value now always is first 1, and then 9, but it could be beneficial to try 9 first, when it is "closer" to the target digit on that dial. This would avoid all the work with the search in the other direction, as it is very probable that the 9-road will lead to a shorter path to the solution when that is the case.

user_54598390
Related