Word Search II
HardTries
You get a grid of letters, board, and a list of distinct words, words. Return every word that can be spelled on the board, in any order, each word once.
A word is spelled by starting on any cell and stepping to a cell above, below, left or right of the last one (not diagonally), reading one letter per cell. One word cannot use the same cell twice.
On this page the board is an array of rows, and each row is an array of one-letter strings.
Examples
Input: board = [["c", "a", "t"], ["x", "r", "e"], ["b", "o", "w"]], words = ["cat", "care", "bow", "row", "tea"] Output: ["cat", "care", "bow", "row"]
care turns down from a to r, then right to e. tea fails: no a touches the e.
Input: board = [["a", "b"], ["c", "d"]], words = ["abdc", "acdb", "ad", "aba"] Output: ["abdc", "acdb"]
a and d touch only at a corner, which does not count, and aba would need the a cell twice.
Constraints
1 ≤ board.length, board[i].length ≤ 121 ≤ words.length ≤ 3 × 10⁴1 ≤ words[i].length ≤ 10- The board and the words use lowercase English letters only, and no word repeats in
words.
Stuck?
Hint 1
Searching the board once per word repeats the same walks. Put all the words in a trie, and one walk from a cell follows every word that starts there at once.
Hint 2
Run a depth-first search from each cell, moving down the trie as you move across the board, and stop when the trie has no child for the next letter. Mark a cell while it is on the current path, and when you reach a node that ends a word, record the word and clear that mark in the trie so it is not recorded twice.
The idea
Searching the board once per word repeats the same walks. Put every word in a trie and walk the board and the trie together. One search from a cell then follows every word that starts there, and turns back as soon as no word continues with the next letter.
Time O(m · n · 4 · 3ᴸ⁻¹) for an m × n board and words up to L lettersExtra space O(total letters in words)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
Build the trie, adding a node for each letter not already on the path. The last node of each word stores the word itself, so reaching that node on the board names the word found.
function findWords(board, words) { const root = {}; for (const word of words) { let node = root; for (const letter of word) { if (!node[letter]) node[letter] = {}; node = node[letter]; } node.word = word; } const rows = board.length; const cols = board[0].length; const found = []; const visit = (r, c, parent) => { const letter = board[r][c]; const node = parent[letter]; if (!node) return; if (node.word) { found.push(node.word); node.word = null; } board[r][c] = '#'; for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr; const nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') visit(nr, nc, node); } board[r][c] = letter; }; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { visit(r, c, root); } } return found;}The trap
Without marking the cells on the current path, a word can step back onto a cell it already used. Words that never need a cell twice come out right, so the search looks complete. A word that repeats a letter can then be spelled by going back and forth between two cells, and it is reported though the board does not hold it.
function findWords(board, words) { const root = {}; for (const word of words) { let node = root; for (const letter of word) { if (!node[letter]) node[letter] = {}; node = node[letter]; } node.word = word; } const rows = board.length; const cols = board[0].length; const found = []; // never marks the cells on the path, so a word can reuse a cell const visit = (r, c, parent) => { const node = parent[board[r][c]]; if (!node) return; if (node.word) { found.push(node.word); node.word = null; } for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const nr = r + dr; const nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) visit(nr, nc, node); } }; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { visit(r, c, root); } } return found;}