LeetCode 212 · Hard · Tries

Word Search II

Given a board of letters and a list of words, return every word that can be traced on the board through horizontally or vertically adjacent cells, using each cell at most once per word.

O(m·n·4^L)time, worst case
O(total letters)space · the trie
trie + backtrackingone walk finds all words

board rows separated by spaces, e.g. oaan etae · up to 4 × 4 letters a–z · 1 to 6 distinct words, 1 to 6 letters each

board path = the cells in visit

Trie of words blue = node of the current word

res words found so far

Set<String> res = new HashSet<>();boolean[][] visit;char[][] board;public List<String> findWords(char[][] board, String[] words) { this.board = board; TrieNode root = new TrieNode(); for (String w : words) { root.addWord(w); } visit = new boolean[board.length][board[0].length]; for (int r = 0; r < board.length; r++) { for (int c = 0; c < board[0].length; c++) { dfs(r, c, root, ""); } } return new ArrayList<>(res);}private void dfs(int r, int c, TrieNode node, String word) { if (r < 0 || c < 0 || r == board.length || c == board[0].length || visit[r][c] || !node.children.containsKey(board[r][c])) { return; } visit[r][c] = true; node = node.children.get(board[r][c]); word += board[r][c]; if (node.isWord) { res.add(word); } dfs(r + 1, c, node, word); dfs(r - 1, c, node, word); dfs(r, c + 1, node, word); dfs(r, c - 1, node, word); visit[r][c] = false;}class TrieNode { Map<Character, TrieNode> children = new HashMap<>(); boolean isWord = false; void addWord(String word) { TrieNode cur = this; for (char c : word.toCharArray()) { if (!cur.children.containsKey(c)) { cur.children.put(c, new TrieNode()); } cur = cur.children.get(c); } cur.isWord = true; }}
r, c
—
word
—
visit
—
res
{}

Why it works

  1. Brute force runs Word Search (79) once per word: a full backtracking pass over the board for each of the k words, O(k · m·n · 4^L). Words with a common prefix re-walk the same cells again and again.
  2. The trie searches all words at once. The board walk moves the trie pointer one letter at a time, so every path is shared by all words with that prefix, and a path dies the moment its letters stop being a prefix of any word (!node.children.containsKey(board[r][c])).
  3. Cost: from each of the m·n cells the walk goes at most L deep with up to 4 (really 3) choices per step: O(m·n·4^L) in the worst case, usually far less because the trie prunes. The trie takes O(total letters); visit and the stack O(L).
  4. Pitfall: forgetting visit[r][c] = false. A cell is off-limits only for the current path; once the walk backs out, other paths may use it again. In "cells used once", aaaa needs all four cells and aaa must not reuse one.
  5. Speed-ups: delete a word's end mark once found and prune trie nodes with no children left, so finished branches are never walked again; and stop early when every word is found.