JS | Backtrack(DFS)
\n//approach: backtracking(dfs)\n//basic template of backtracking would be to loop, choose, explore and unchoose\n//loop: you want to iterate over all the numbe
```\n//approach: backtracking(dfs)\n//basic template of backtracking would be to loop, choose, explore and unchoose\n//loop: you want to iterate over all the numbers so that you can find it\'s possible values\n//choose: you start with the index value(the 0th index number), so that you can find the next combined possible values for the 0th value\n//explore: basically recursion to add all the next values to the 0th value\n//unchoose: you pop the value (Oth value), so then you can now start with other value to make that other value 0th value\n//in this case: \n//since its a 2D array, instead of looping once, we will loop twice, over the row and column of the board\n//then to choose, we will just mark the visited index with \'*\'\n//to explore, we will be exploring left, right, up, down of the board from the current spot/box\n//then to unchoose, we will just replace the \'*\' with the letter we had replaced\n//\n//so basically, \n//we will start from the [0][0] of the board, and start checking if the letter in that spot is equal to the letter in the given word\n//if it is equal, we recurse to find possible matching letter from the board\n//we increment the wordIndex by 1, we also replace the spot with \'*\' \n//and then backtrack check to see if the neighbors(left, right, up, down) have the new letter from the given word\n//if somehow the boundary check fails or the letter check fails, we return false, \n//if all of the check fails while backtracking we start replacing the \'*\' with the actual letters we stored in our temp variable\n//then return the result back.\nvar exist = function(board, word) {\n    if(board == null || word == null || board.length == 0) //edge case\n        return false;\n    \n    \n    for(let row = 0; row < board.length; row++){\n        for(let col = 0; col < board[0].length; col++){\n            if(helper(board, word, row, col, 0))  //recursive check\n                return true;\n        }\n    }\n    \n    \n    function helper(board, word, row, col, wordIndex){\n        \n        if(wordIndex == word.length) \n            return true;\n        \n        //out of bounds check\n        if(row < 0 || row >= board.length || col < 0  || col >= board[0].length)\n            return false;\n        \n        //letter check in the box (if the letter at the board is not equal to the letter of the given word return false)\n        if(board[row][col] != word[wordIndex])\n            return false;\n        \n        //choose\n        let temp = board[row][col];\n        board[row][col] = \'*\';          //marking the visited box\n        \n        //explore\n        let bool = helper(board, word, row-1, col, wordIndex+1) ||\n            helper(board, word, row+1, col, wordIndex+1) ||\n            helper(board, word, row, col-1, wordIndex+1) ||\n            helper(board, word, row, col+1, wordIndex+1);\n    \n        //unchoose\n        board[row][col] = temp;        //setting back the value from \'*\' to the letter\n        \n        return bool;\n    }\n    \n    \n    return false;\n};\n```
['Backtracking', 'Recursion', 'JavaScript']