Pattern visualizer
Word Search II
Searching the board once per word re-walks shared prefixes over and over - 'oath' and 'oat' would retrace the same first three cells. Building one Trie out of all the words fixes that: from any board cell, look up whether the current Trie node has a child for that letter. If it does, step into both the Trie and the board together and keep going in 4 directions; if it does not, that branch can never spell a word, so stop immediately. A Trie node with a completed word is reported once and then cleared, so revisiting the same letters later can never report it twice. Animated on: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]. Answer: ["oath", "eat"]..
One Trie, one board DFS, chasing every word at once
Build one Trie from "oath", "pea", "eat", "rain", then scan every cell of the 4x4 board. Whenever a cell's letter matches a Trie child of the current node, step into the Trie and the board together — this lets one DFS chase all 4 words at once instead of re-scanning the board per word.
1FUNCTION findWords(board, words)2 trie <- BUILD TRIE FROM words3 FOR EACH cell (r, c) ON board4 dfs(r, c, trie.root, path <- EMPTY)5 FUNCTION dfs(r, c, node, path)6 IF node.children DOES NOT CONTAIN board[r][c]: RETURN7 node <- node.children[board[r][c]]8 APPEND board[r][c] TO path9 IF node.word != NULL: ADD node.word TO found; node.word <- NULL10 FOR EACH unvisited neighbour (nr, nc)11 dfs(nr, nc, node, path)12 REMOVE LAST FROM path13 RETURN found
← / → step · space play · Home restart