This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

TODAY JAVASCRIPT BROKE ME!!!! HORRAY!!!
allow me to walk you through this painfully wasted 3+ hours of my life :(

The question is given a m by n matrix of string, try to find the a given word in the matrix. The word in matrix can only be connected via up, down, left, or right of a cell. The word also have to be in order in the matrix too. For example, see can be:
see,
ees,
s
e
e,
s
e e
or any other way, but cannot be say:
s
_e
__e
(can't have leading white space in this editor :P)

Now that we have understood the problem let's break down how to do the problem

The first thing we know is that we'll definitely need a double nested for loop for this problem. This is just so that we can find the first letter of the given word in the matrix. Note that we definitely can have more than one of the first letter in the matrix, so there is really no getting away from the double nested for loop.

once we find a first letter of given word, we can then start checking if its neighboring and its neighbor's neighbor has the the subsequent strings.

Therefore to do this right, we'll need recursion to travel through the matrix. At each recursion, we'll check up, down, left, and right of the give position. We will want to prevent infinite loop such as when [1,0 <-> 0,0], so we'll need a map that keeps track of the visited cell.

By now if the idea of backtracking hasn't occurred to you, then it's time for a googling on the concept, this is essential in the question.

Lastly, we'll to keep track of on which index of the given word we are concerned about. This is because we care about the order of the word, otherwise we could just use a map.

So we'll need:
1.) a visited map
2.) a variable keeping track of index of word we care about
3.) double nested for loop to iterate through the entire matrix.
4.) a recursion function to travel through the matrix

at each recursion it should do the following:
1.) check if the given row and col variable is outside of matrix
2.) return true if the index variable of given word is at word.length.

3.) check if the given row and col is already visited
4.) check if the given row and col correspond to the current index of given word
5.) when the code reaches this point, it means the current row and col corresponds to the correct index string of the given word, so we should:
5a.) mark row col visited
5b.) increment index of given string
5c.) go into next recursion
if the code hasn't returned true at 5c, it means we are backtracking, so we should:
5d.) unmark row col visited
5e.) decrement index of given string

5d and 5e is the backtracking part.

the code is below:

var exist = function(board, word) {
    let visited = {};
    let wordI = 0;

    for (let row=0; row<board.length; row++) {
        for (let col=0; col<board[0].length; col++) {
            visited = {};
            if(board[row][col] === word[wordI]) {
                visited[`${row}:${col}`] = true;
                wordI++;

                if(findWord(row, col)) { return true; }
                else {
                    visited[`${row}:${col}`] = false;
                    wordI--;
                }
            }
        }
    }

    function findWord (row, col) {
        if(wordI === word.length) return true;

        // if(visitCell(row+1, col)) { return true } 
        // if(visitCell(row, col+1)) { return true } 
        // if(visitCell(row-1, col)) { return true } 
        // if(visitCell(row, col-1)) { return true } 

        for (i of [1,-1]) {
            if(visitCell(row+i, col)) { return true } 
            if(visitCell(row, col+i)) { return true } 
        }
    }

    function visitCell (rowI, colI) {
        if(!board[rowI] || !(board[rowI][colI])) return false; 

        const key=`${rowI}:${colI}`;
        const letter = board[rowI][colI];

        if(word[wordI] === letter && !visited[key]) {
            wordI++;
            visited[key] = true

            if(findWord(rowI, colI)) { return true };

            wordI--;
            visited[key] = false
        }
        return false;
    }

    return false;
};

Now you may ask, what's with the commented section ? It's the same as the for loop. Well...you are right, it SHOULD be the same. Except for one small detail... I'll let you figure it out for a bit and when you think you know scroll down
.

.

.

.

.

.

.

.

.

.

.

.

.

the answer is that I forgot to do:
let i = ... and was just i. In javascript, this i variable then becomes the global and somewhere down the line (probably in the interpreter?) someone also did the same stupid mistake and mutated my variable.

My code passed with poor performance, I checked with the good performance submission, it seems to be that I had two functions for the recursion. So the overhead of the recursion made my algorithm a lot slower than others. It is all correct otherwise :)

Let me know anything on your mind after reading through this, THANKS!