168. Word Search II

Put all the words into a trie so a single DFS from each board cell can check many words at once — the DFS only continues down paths that the trie says could still spell a word. When the DFS reaches a trie node marked as a word end, record that word.

Idea

Searching each word independently is wasteful. Instead build a trie of all the words; then a DFS from each cell walks the board and the trie together. At each step we only recurse into neighbors whose character is a child in the current trie node — so dead ends are pruned immediately. Reaching a trie node that stores a word means we found it.

Mark visited cells (e.g. set to '#') during the DFS and restore them on backtrack. Collect found words in a set to avoid duplicates.

Algorithm

1. Insert every word into a trie; store the full word at its terminal node.
2. For each cell, DFS carrying the current trie node:
   • If the cell's char isn't a child of the node, stop.
   • Move to that child; if it holds a word, add it to the result.
   • Mark the cell visited, recurse into the four neighbors, then restore.
3. Return the found words (sorted for a stable order).

Worked example

On the 4×4 board with words ["oath","pea","eat","rain"], the DFS finds "eat" and "oath".

Complexity

• Time: O(m·n·4^L) worst case (L = max word length), heavily pruned by the trie.
• Space: O(total characters in words) for the trie.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

class Solution {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        String word = null;
    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                node = node.children.computeIfAbsent(c, x -> new TrieNode());
            }
            node.word = w;
        }
        int m = board.length, n = board[0].length;
        TreeSet<String> result = new TreeSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root, result);
            }
        }
        return new ArrayList<>(result);
    }

    private void dfs(char[][] board, int i, int j, TrieNode node, TreeSet<String> result) {
        char c = board[i][j];
        if (c == '#' || !node.children.containsKey(c)) {
            return;
        }
        TrieNode nxt = node.children.get(c);
        if (nxt.word != null) {
            result.add(nxt.word);
        }
        board[i][j] = '#';
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
                dfs(board, ni, nj, nxt, result);
            }
        }
        board[i][j] = c;
    }
}