Approach: Trie (Prefix Tree) Backtracking DFSBuild a Trie from“words”, then DFS from every cell on the board. Three pruning tricks make it fast enough:Bail out when the prefix dies — if“children[ch]” is null, stop immediatelyNull out the word once found — set“node.word null” so the same word isn’t collected twiceDetach exhausted subtrees — once every word under a node has been found, cut the parent’s pointer to itclass Solution {static class TrieNode {TrieNode[] children new TrieNode[26];String word; // non-null: a complete word ends here}private final TrieNode root new TrieNode(); private final ListString res new ArrayList(); private static final int[][] DIRS {{1,0},{-1,0},{0,1},{0,-1}}; private char[][] board; private int m, n; public ListString findWords(char[][] board, String[] words) { this.board board; this.m board.length; this.n board[0].length; for (String w : words) insert(w); for (int i 0; i m; i) for (int j 0; j n; j) dfs(i, j, root, new boolean[m][n]); return res; } private void insert(String word) { TrieNode cur root; for (char c : word.toCharArray()) { int k c - a; if (cur.children[k] null) cur.children[k] new TrieNode(); cur cur.children[k]; } cur.word word; } private void dfs(int r, int c, TrieNode parent, boolean[][] visited) { if (r 0 || r m || c 0 || c n || visited[r][c]) return; char ch board[r][c]; TrieNode node parent.children[ch - a]; if (node null) return; // prune 1: dead prefix if (node.word ! null) { res.add(node.word); node.word null; // prune 2: dedupe } if (isEmpty(node)) { // prune 3: subtree drained parent.children[ch - a] null; return; } visited[r][c] true; for (int[] d : DIRS) dfs(r d[0], c d[1], node, visited); visited[r][c] false; // backtrack } private boolean isEmpty(TrieNode node) { for (TrieNode child : node.children) if (child ! null) return false; return node.word null; }}ComplexityTime:“O(Σ|word|)” to build the Trie; search is“O(m·n·4·3^(L-1))” worst case where“L” is the longest word length, but pruning keeps real runs far below thatSpace:“O(Σ|word|)” for the Trie, plus“O(m·n)” for the recursion stack and visited arrayTwo optional micro-optimizationsDrop the visited array: temporarily flip a visited cell to“‘#’” and restore it on backtrack, saving an extra arrayAvoid the“O(26)” scan in“isEmpty”: give“TrieNode” an“int count” of remaining words in its subtree, decrement on collection, and detach the pointer when it hits 0One pitfall worth noting: don’t collect into a“Set” and skip prune 2 — on heavily overlapping prefixes like““aaa”” that gets noticeably slower.
