Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”] Output: [“eat”,“oath”]

Example 2:

Input: board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”] Output: []

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Approach: Trie + Backtracking (DFS)

Algorithm

1. Build a trie of all the target words so that board exploration can share prefixes
2. From every cell, run DFS: check the current cell’s letter against the trie node’s children
3. When a node has isEnd set, record the word and clear the flag to avoid duplicates
4. Mark the current cell visited (or swap it with a placeholder) before recursing, and restore it afterward
5. Prune branches once no child matches or the node has no words below it

Time & Space Complexity

• Time Complexity: O(M * N * 4 * 3^(L-1)) - up to 4 directions from the start and 3 afterward, where L is the max word length
• Space Complexity: O(W * L) - the trie for all words

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class WordSearchII {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }

    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    /**
     * Find all words from the list that exist on the board.
     * @param board Character board
     * @param words List of target words
     * @return Words found on the board
     */
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.word = w;
        }

        List<String> result = new ArrayList<>();
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root, result);
            }
        }
        return result;
    }

    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }

        char c = board[i][j];
        if (c == '#' || node.children[c - 'a'] == null) {
            return;
        }

        node = node.children[c - 'a'];
        if (node.word != null) {
            result.add(node.word);
            node.word = null;
        }

        board[i][j] = '#';
        for (int[] d : DIRS) {
            dfs(board, i + d[0], j + d[1], node, result);
        }
        board[i][j] = c;
    }

    // Test method
    public static void main(String[] args) {
        WordSearchII ws = new WordSearchII();
        char[][] board = {
            {'o', 'a', 'a', 'n'},
            {'e', 't', 'a', 'e'},
            {'i', 'h', 'k', 'r'},
            {'i', 'f', 'l', 'v'}
        };
        String[] words = {"oath", "pea", "eat", "rain"};
        System.out.println("Input: words = [\"oath\",\"pea\",\"eat\",\"rain\"]");
        System.out.println("Output: " + ws.findWords(board, words)); // Expected: [eat, oath]
    }
}

Example Walkthrough

Starting DFS from every cell with trie root:

1. From (0,0)=‘o’, explore children; ‘o’ exists in the trie. Continue through ‘a’,‘t’,‘h’ to complete “oath”
2. From (1,0)=‘e’, follow ‘e’,‘a’,‘t’ to complete “eat”
3. “pea” and “rain” fail because no matching path covers the full trie word
4. Each found word’s node.word is nulled, so it is reported exactly once

Final output: ["eat","oath"].

Key Points

1. Trie Shares Prefixes: All words share one structure, avoiding repeated work across words
2. word Field: Storing the full word at the terminal node makes collection trivial
3. In-Place Visited: Replacing the cell with '#' marks it visited, restoring afterward
4. Duplicate Prevention: Clearing node.word after collection prevents double reports
5. Early Pruning: A missing trie child or a visited cell immediately ends that branch