Word Search II

Free with account Updated Nov 19, 2026 · 8 min read
On this page

    Problem statement

    You get a grid of letters and a list of words. Return every word from the list that can be traced on the grid. A word is traced by starting at any cell and moving up, down, left or right to the next letter, without using the same cell twice in that word. Return each found word once, in any order.

    This is the hard version of Word Search. A grid DFS alone is not enough here: the question is really about sharing work across many words, and the trie is the tool for that. Original problem: LeetCode 212.

    Example

    On the 4×4 grid, "oath" is traced o → a → t → h and "eat" is traced e → a → t. "pea" and "rain" cannot be traced, so the output is ["oath", "eat"].
    On the 4×4 grid, "oath" is traced o → a → t → h and "eat" is traced e → a → t. "pea" and "rain" cannot be traced, so the output is ["oath", "eat"].
    Input:  board = [["o","a","a","n"],
                     ["e","t","a","e"],
                     ["i","h","k","r"],
                     ["i","f","l","v"]]
            words = ["oath", "pea", "eat", "rain"]
    Output: ["oath", "eat"]      # any order
    Input:  board = [["a","b"],["c","d"]], words = ["abcb"]
    Output: []                   # "b" would have to be used twice

    Constraints (assumed)

    • 1 ≤ rows, columns ≤ 12.
    • 1 ≤ number of words ≤ 30,000, each 1 to 10 lowercase letters, all distinct.

    What this question tests

    • Recognizing that running Word Search once per word repeats the same work, and that a trie shares common prefixes across all words.
    • Backtracking on a grid: marking a cell as used and restoring it.
    • Practical pruning: removing found words and empty trie branches.

    Questions to ask first

    1. Can a cell be reused within one word? (No.) Across different words? (Yes, each word is traced independently.)
    2. Are diagonal moves allowed? (No: up, down, left, right.)
    3. Can the word list contain duplicates, and should the output? (Return each word once.)
    4. How big are the board and the list? Thousands of words is the signal to share work with a trie.