Pattern visualizer
Word Search II (Trie)
Searching the board once per word re-walks shared prefixes over and over. Inserting every word into one trie fixes that: a trie node's id is the prefix it spells, so words that start the same way share the same nodes. From any board cell, look up whether the trie node the DFS is currently at has a child for that letter. If it does, step into both the trie and the board together in one recursive call; if it does not, that branch can never spell a word, so stop immediately instead of exploring it. A trie node with `end` true is reported once and its word cleared, so a second board path to the same node 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 shared trie, one board DFS, chasing every word at once
Insert "oath", "pea", "eat", "rain" into one shared trie before touching the board. Shared prefixes share nodes: "oath" and "eat" both need an 'a' after their first letter, but that letter is a different trie node here because their first letters differ. Then scan every cell of the 4x4 board; a cell only starts a search when the trie's root has a child for that letter.
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.end = TRUE: ADD node.word TO found; node.end <- FALSE10 FOR EACH unvisited neighbour (nr, nc)11 dfs(nr, nc, node, path)12 REMOVE LAST FROM path13 RETURN found
← / → step · space play · Home restart