Word Search II

Problem#

Given an m x n board of letters and a dictionary of words, return all dictionary words present on the board. A word can be built from sequentially adjacent cells (up/down/left/right) and each cell may not be reused within a single word.

Examples#

board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] → ["oath","eat"].

Constraints#

1 <= m, n <= 12, 1 <= words.length <= 3 * 10^4, 1 <= words[i].length <= 10.

Hints#

Hint 1

Searching each word independently is too slow — share traversal via a trie of all words.

Hint 2

Prune subtrees of the trie as soon as a word is matched, so duplicates aren’t re-discovered.

Approach#

Per-word DFS — O(W * M * N * 4^L). Too slow when W is large.

Trie + grid DFS — build trie of all words, walk grid once; each path follows trie children only.

DFS from every cell, descending in the trie. When you hit a trie node with a word field set, collect it and null the field to dedupe. Prune leaf trie nodes after collection to shrink future work.

Solution#

class Solution {
    struct Node {
        Node* child[26]{};
        string word;            // non-empty iff this node is a word end
    };
    void insert(Node* root, const string& w) {
        Node* cur = root;
        for (char c : w) {
            int i = c - 'a';
            if (!cur->child[i]) cur->child[i] = new Node();
            cur = cur->child[i];
        }
        cur->word = w;
    }
    void dfs(vector<vector<char>>& b, int r, int c, Node* node, vector<string>& out) {
        char ch = b[r][c];
        if (ch == '#' || !node->child[ch - 'a']) return;
        Node* next = node->child[ch - 'a'];
        if (!next->word.empty()) { out.push_back(next->word); next->word.clear(); }
        b[r][c] = '#';
        if (r + 1 < (int)b.size())    dfs(b, r + 1, c, next, out);
        if (r - 1 >= 0)               dfs(b, r - 1, c, next, out);
        if (c + 1 < (int)b[0].size()) dfs(b, r, c + 1, next, out);
        if (c - 1 >= 0)               dfs(b, r, c - 1, next, out);
        b[r][c] = ch;
        // Optional pruning: detach leaf trie nodes.
        bool empty = true;
        for (int i = 0; i < 26; ++i) if (next->child[i]) { empty = false; break; }
        if (empty && next->word.empty()) node->child[ch - 'a'] = nullptr;
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Node* root = new Node();
        for (auto& w : words) insert(root, w);
        vector<string> ans;
        for (int r = 0; r < (int)board.size(); ++r)
            for (int c = 0; c < (int)board[0].size(); ++c)
                dfs(board, r, c, root, ans);
        return ans;
    }
};

type trieNode struct {
    child [26]*trieNode
    word  string
}

func findWords(board [][]byte, words []string) []string {
    root := &trieNode{}
    insert := func(w string) {
        cur := root
        for i := 0; i < len(w); i++ {
            idx := w[i] - 'a'
            if cur.child[idx] == nil {
                cur.child[idx] = &trieNode{}
            }
            cur = cur.child[idx]
        }
        cur.word = w
    }
    for _, w := range words {
        insert(w)
    }
    m, n := len(board), len(board[0])
    ans := []string{}
    var dfs func(r, c int, node *trieNode)
    dfs = func(r, c int, node *trieNode) {
        ch := board[r][c]
        if ch == '#' || node.child[ch-'a'] == nil {
            return
        }
        next := node.child[ch-'a']
        if next.word != "" {
            ans = append(ans, next.word)
            next.word = ""
        }
        board[r][c] = '#'
        if r+1 < m {
            dfs(r+1, c, next)
        }
        if r-1 >= 0 {
            dfs(r-1, c, next)
        }
        if c+1 < n {
            dfs(r, c+1, next)
        }
        if c-1 >= 0 {
            dfs(r, c-1, next)
        }
        board[r][c] = ch
        // Optional pruning: detach leaf trie nodes.
        empty := true
        for i := 0; i < 26; i++ {
            if next.child[i] != nil {
                empty = false
                break
            }
        }
        if empty && next.word == "" {
            node.child[ch-'a'] = nil
        }
    }
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            dfs(r, c, root)
        }
    }
    return ans
}

from typing import List

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trie: dict = {}
        for w in words:
            cur = trie
            for ch in w:
                cur = cur.setdefault(ch, {})
            cur['$'] = w  # word end marker

        m, n = len(board), len(board[0])
        ans: List[str] = []

        def dfs(r: int, c: int, node: dict) -> None:
            ch = board[r][c]
            if ch not in node:
                return
            nxt = node[ch]
            if '$' in nxt:
                ans.append(nxt['$'])
                del nxt['$']
            board[r][c] = '#'
            if r + 1 < m:
                dfs(r + 1, c, nxt)
            if r - 1 >= 0:
                dfs(r - 1, c, nxt)
            if c + 1 < n:
                dfs(r, c + 1, nxt)
            if c - 1 >= 0:
                dfs(r, c - 1, nxt)
            board[r][c] = ch
            # Optional pruning: detach leaf trie nodes.
            if not nxt:
                del node[ch]

        for r in range(m):
            for c in range(n):
                dfs(r, c, trie)
        return ans

function findWords(board, words) {
    const trie = {};
    for (const w of words) {
        let cur = trie;
        for (const ch of w) {
            if (!cur[ch]) cur[ch] = {};
            cur = cur[ch];
        }
        cur['$'] = w; // word end marker
    }
    const m = board.length, n = board[0].length;
    const ans = [];
    const dfs = (r, c, node) => {
        const ch = board[r][c];
        if (!node[ch]) return;
        const nxt = node[ch];
        if (nxt['$']) {
            ans.push(nxt['$']);
            delete nxt['$'];
        }
        board[r][c] = '#';
        if (r + 1 < m) dfs(r + 1, c, nxt);
        if (r - 1 >= 0) dfs(r - 1, c, nxt);
        if (c + 1 < n) dfs(r, c + 1, nxt);
        if (c - 1 >= 0) dfs(r, c - 1, nxt);
        board[r][c] = ch;
        // Optional pruning: detach leaf trie nodes.
        if (Object.keys(nxt).length === 0) delete node[ch];
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            dfs(r, c, trie);
        }
    }
    return ans;
}

class TrieNode {
    TrieNode[] child = new TrieNode[26];
    String word;
}

class Solution {
    private char[][] board;
    private List<String> ans = new ArrayList<>();
    private int m, n;

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        m = board.length;
        n = board[0].length;
        TrieNode root = new TrieNode();
        for (String w : words) insert(root, w);
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dfs(r, c, root);
            }
        }
        return ans;
    }

    private void insert(TrieNode root, String w) {
        TrieNode cur = root;
        for (int i = 0; i < w.length(); i++) {
            int idx = w.charAt(i) - 'a';
            if (cur.child[idx] == null) cur.child[idx] = new TrieNode();
            cur = cur.child[idx];
        }
        cur.word = w;
    }

    private void dfs(int r, int c, TrieNode node) {
        char ch = board[r][c];
        if (ch == '#' || node.child[ch - 'a'] == null) return;
        TrieNode next = node.child[ch - 'a'];
        if (next.word != null) {
            ans.add(next.word);
            next.word = null;
        }
        board[r][c] = '#';
        if (r + 1 < m) dfs(r + 1, c, next);
        if (r - 1 >= 0) dfs(r - 1, c, next);
        if (c + 1 < n) dfs(r, c + 1, next);
        if (c - 1 >= 0) dfs(r, c - 1, next);
        board[r][c] = ch;
        boolean empty = true;
        for (int i = 0; i < 26; i++) {
            if (next.child[i] != null) {
                empty = false;
                break;
            }
        }
        if (empty && next.word == null) node.child[ch - 'a'] = null;
    }
}

function findWords(board: string[][], words: string[]): string[] {
    type TrieNode = { [key: string]: TrieNode | string | undefined; $?: string };
    const trie: TrieNode = {};
    for (const w of words) {
        let cur: TrieNode = trie;
        for (const ch of w) {
            if (!cur[ch]) cur[ch] = {};
            cur = cur[ch] as TrieNode;
        }
        cur['$'] = w; // word end marker
    }
    const m = board.length, n = board[0].length;
    const ans: string[] = [];
    const dfs = (r: number, c: number, node: TrieNode): void => {
        const ch = board[r][c];
        if (!node[ch]) return;
        const nxt = node[ch] as TrieNode;
        if (nxt['$']) {
            ans.push(nxt['$']);
            delete nxt['$'];
        }
        board[r][c] = '#';
        if (r + 1 < m) dfs(r + 1, c, nxt);
        if (r - 1 >= 0) dfs(r - 1, c, nxt);
        if (c + 1 < n) dfs(r, c + 1, nxt);
        if (c - 1 >= 0) dfs(r, c - 1, nxt);
        board[r][c] = ch;
        // Optional pruning: detach leaf trie nodes.
        if (Object.keys(nxt).length === 0) delete node[ch];
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            dfs(r, c, trie);
        }
    }
    return ans;
}

Editorial#

Sharing prefixes across the dictionary is the win — a single grid DFS now matches as many words as fit each path’s prefix. Clearing node->word after a hit prevents duplicates; pruning empty leaf nodes shrinks the trie as words are consumed, making later cells faster.

Complexity#

Time: O(M * N * 4^L) worst case (L = max word length).
Space: O(W * L) for the trie.

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#