Find a grid path spelling a word with ? wildcard letters
A word-snake puzzle shows a grid of letters. Players drag their finger from cell to cell to spell a word, and the game highlights the path they traced. When a player asks for a hint, the game must find a path for the hidden word, or say there is none. Hint words may contain ? for letters the game does not want to give away.
Implement traceWord(grid, word). It returns the cells of one path that spells word, or null if no such path exists.
traceWord(grid, word) // => Array<[row, col]> | null
grid is a rectangular 2D array of single lowercase letters. It can be empty ([]).word is a string of lowercase letters and ? characters.word. Each cell must be directly above, below, left or right of the previous one (no diagonals).word must equal the letter in its cell exactly (case-sensitive). A ? matches any cell.[row, col] pairs, in the order the word is spelled. If several paths exist, return any one of them.null when no path exists. The empty word returns [].grid. If you mark visited cells by changing the grid, restore them before returning.const grid = [
['c', 'a', 't', 's'],
['o', 'r', 'e', 'x'],
['d', 'o', 'g', 's'],
];
traceWord(grid, 'cat'); // => [[0, 0], [0, 1], [0, 2]]
traceWord(grid, 'care'); // => [[0, 0], [0, 1], [1, 1], [1, 2]]
traceWord(grid, 'cod'); // => [[0, 0], [1, 0], [2, 0]]
traceWord(grid, 'd?g'); // => [[2, 0], [2, 1], [2, 2]]
traceWord(grid, 'cr'); // => null (diagonal moves are not allowed)
traceWord(grid, 'cog'); // => null
traceWord(grid, 'CAT'); // => null (case-sensitive)
traceWord(grid, ''); // => []
traceWord([['a', 'b']], 'aba'); // => null (the a cell cannot be reused)
When a word can be traced, tests do not compare against one specific path. They check that your path has one cell per character, every cell is inside the grid, consecutive cells are neighbours, no cell repeats, and every cell matches its character.