Course4all
Join us on telegram
Home/dsa/Trie/Word Search II

Word Search II

Master this topic with zero to advance depth.

Word Search II

The Challenge of Multiple Words

If we have KK words, running a standard Word Search (DFS) for each word takes O(K⋅M⋅N⋅3L)O(K \cdot M \cdot N \cdot 3^L). This is inefficient because many words share prefixes (e.g., 'apple' and 'apply').

Trie for Prefix Sharing

By storing the dictionary in a Trie, we can search for all words simultaneously. As we traverse the grid in DFS, we also traverse the Trie. If a path in the grid doesn't match any prefix in the Trie, we prune the search immediately.

Optimization: Trie Pruning

Once a word is found, we can remove it from the Trie (or mark it as found) and potentially delete leaf nodes that are no longer part of any other words. This drastically reduces the search space for subsequent cells.

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. Includes visual Trie-based pruning trace. The same letter cell may not be used more than once in a word.

Hard

Examples

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"]
Approach 1

Level I: Naive DFS (Multiple Word searches)

Intuition

Iterate through each word in the list and perform a standard DFS search on the board.

For each word in words, scan every cell (r, c). If board[r][c] == word[0], start a DFS to find the rest of the characters.

⏱ O(K * M * N * 3^L) where K is number of words, L is max length.💾 O(L) for recursion depth.

Detailed Dry Run

Searching 'oath'. Find 'o' at (0,0). Neighbors: (0,1) 'a'. Next: (1,1) 't'. Next (0,1) NO, (0,2) NO, (1,0) NO... SUCCESS.

java
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (exist(board, word)) result.add(word);
        }
        return result;
    }
    private boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                if (dfs(board, i, j, word, 0)) return true;
        return false;
    }
    private boolean dfs(char[][] board, int r, int c, String word, int i) {
        if (i == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(i)) return false;
        char temp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, r+1, c, word, i+1) || dfs(board, r-1, c, word, i+1) || 
                        dfs(board, r, c+1, word, i+1) || dfs(board, r, c-1, word, i+1);
        board[r][c] = temp;
        return found;
    }
}
Approach 2

Level II: Backtracking with Trie

Intuition

Insert all words into a Trie. Traverse the board and the Trie simultaneously to find matches.

Starting at each cell, if the character exists as a child of the Trie root, move into the Trie. If node.isEndOfWord, add the word to result.

⏱ O(M * N * 3^L)💾 O(Total chars in words) for Trie.

Detailed Dry Run

Trie: root -> o -> a -> t -> h (END). At (0,0) 'o': matches root.child('o'). Neighbors of (0,0): 'a' at (0,1) matches 'o'.child('a'). Neighbors of (0,1): 't' at (1,1) matches 'a'.child('t')...

java
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null;
}
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode curr = root;
            for (char c : w.toCharArray()) {
                if (curr.children[c - 'a'] == null) curr.children[c - 'a'] = new TrieNode();
                curr = curr.children[c - 'a'];
            }
            curr.word = w;
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                dfs(board, i, j, root, res);
        return res;
    }
    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> res) {
        char ch = board[r][c];
        if (node.children[ch - 'a'] == null) return;
        node = node.children[ch - 'a'];
        if (node.word != null) {
            res.add(node.word);
            node.word = null;
        }
        board[r][c] = '#';
        int[] dr = {0, 0, 1, -1}, dc = {1, -1, 0, 0};
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length && board[nr][nc] != '#')
                dfs(board, nr, nc, node, res);
        }
        board[r][c] = ch;
    }
}
Approach 3

Level III: Optimized Trie (Node Removal)

Intuition

When a leaf node is found and its word is extracted, if it has no children, we can delete the node from its parent to avoid re-visiting dead branches.

Add a parent pointer or count to each node. When word != "", set it to null. If children count becomes 0, remove the entry from search path completely.

⏱ O(M * N * 3^L) with significantly better early exit.💾 O(Total chars).

Detailed Dry Run

Trie: root -> o -> a -> t -> h (END). After finding 'oath', the path 'h' -> 't' -> 'a' -> 'o' is pruned if no other words use them. Subsequent board scans will skip 'o' immediately.

java
import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; String word = null; }
    public List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node curr = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (curr.children[i] == null) curr.children[i] = new Node();
                curr = curr.children[i];
            }
            curr.word = w;
        }
        List<String> result = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) dfs(board, r, c, root, result);
        }
        return result;
    }
    private void dfs(char[][] board, int r, int c, Node node, List<String> res) {
        char ch = board[r][c];
        if (ch == '#' || node.children[ch - 'a'] == null) return;
        node = node.children[ch - 'a'];
        if (node.word != null) { res.add(node.word); node.word = null; }
        board[r][c] = '#';
        int[] dr = {0, 0, 1, -1}, dc = {1, -1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length) dfs(board, nr, nc, node, res);
        }
        board[r][c] = ch;
    }
}
← Previous QuestionReplace Words
Next Question →Design Search Autocomplete System