JS | Backtracking | Read this if you are having problems using a Set
I spent some time confused as to why my solution, which was seamingly very similar to other\'s in Java and Python was not working. There are two main ways to so
I spent some time confused as to why my solution, which was seamingly very similar to other\'s in Java and Python was not working. There are two main ways to solve this problem with backtracking: changing the value of the board when visiting a position, or keeping a record of your visited positions and check against it. \n\nA Set is a great data structure for that record of visited positions. There is a caveat, however. In JavaScript, values put into the Set are stored by reference, so when looking them up, if you pass anything else other than the same reference, your item wont be found.\n\nWhy is this relevant?\n\n```\nconst set = new Set();\n//.....\nconst arr = [1,4]\nset.add(arr);\n\nset.has(arr) // true\nset.has([1,4]) // false!\n\n```\nAs you can see, looking up an array (or object) by values does not work, since when we pass the `[1,4]` array, we are essentially creating a new array, so the references are different.\n\nTo solve this, you have to convert your array to a unique value. I converted the coordinate array to a string with an "r|c" format. \n\nKeep in mind that the way in which you convert your array to a unique value has a runtime impact. Avoid `array.join()` or other iterartive approaches if possible.\n\nI hope this is helpful to anyone trying to implement this with a Set.\n\n```\n/**\n * @param {character[][]} board\n * @param {string} word\n * @return {boolean}\n */\nvar exist = function(board, word) {\n    \n    const M = board.length;\n    const N = board[0].length;\n    \n    const path = new Set();\n    \n    function backtrack(r,c,idx){\n        \n        if(idx === word.length) return true;\n        if(r < 0 || c < 0 || r >= M || c >= N) return false;\n        if(board[r][c] !== word.charAt(idx)) return false;\n        \n        const arrStr = `${r}|${c}`;\n        if(path.has(arrStr)) return false;\n        \n        path.add(arrStr);\n        const found = \n              backtrack(r+1, c, idx+1) ||\n              backtrack(r-1,c,idx+1) || \n              backtrack(r,c+1, idx+1) ||               \n              backtrack(r,c-1, idx+1);\n        path.delete(arrStr);            \n        return found;\n    \n    }\n   \n    \n    for(let i = 0; i<M; i++){\n        for(let j = 0; j<N; j++){\n            if(board[i][j] === word.charAt(0))\n                if(backtrack(i,j,0)) return true;        \n        }\n    }\n\t\n    return false;\n}
['Backtracking', 'Ordered Set', 'JavaScript']