Coding interview problems › Design & Tries

🗃️ Design & Tries Hard

Word Search II

Word Search II explained: put all words in a trie and run one backtracking DFS per grid cell, pruning dead prefixes, with tested Python and a live trie visual.

Also searched as: word search II trie · find all dictionary words in a grid · boggle solver

🌲

Try it live Free

Trie & Autocomplete

Watch the trie share common prefixes as words branch in; Word Search II walks those shared branches once while exploring the grid, instead of once per word.

Also useful: Backtracking: Subsets, Permutations & Pruning, Number of Islands & Grid BFS

Open the playground →

The problem

Given a grid of letters and a list of words, return every word from the list that can be traced in the grid through horizontally or vertically adjacent cells, using each cell at most once per word. This is the logic behind a Boggle solver.

Inputboard = ["oaan", "etae", "ihkr", "iflv"], words = ["oath", "pea", "eat", "rain"]
Output["eat", "oath"]
Inputboard = ["ab", "cd"], words = ["abcb"]
Output[]

The key insight

Running Word Search once per word repeats the same exploration for words that share prefixes. Instead, put all words into a trie and do one DFS from each cell that walks the grid and the trie together. The moment the current path is not a prefix of any word, stop. When you reach a node that ends a word, record it.

Brute force first: Calling the single-word search for each of k words costs about k × m × n × 3L.

Step-by-step approach

  1. Insert every word into a trie, storing the full word at its end node.
  2. For each cell, start a DFS with the root's child for that cell's letter.
  3. In the DFS, if the node holds a word, add it to the results and clear it so it is not reported twice.
  4. Mark the cell as used, recurse into the four neighbours whose letters are children of the current node, then restore the cell.
  5. Optionally remove trie nodes whose children have all been used up, which prunes later searches.

Python solution

PYTHON 3tested
def find_words(board, words):
    root = {}
    for w in words:                       # build trie of nested dicts
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = w                     # "$" marks a complete word
    grid = [list(r) for r in board]
    rows, cols = len(grid), len(grid[0]) if grid else 0
    found = []

    def dfs(r, c, parent):
        ch = grid[r][c]
        node = parent[ch]
        if "$" in node:
            found.append(node.pop("$"))   # record once
        grid[r][c] = "#"                  # mark in use
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] in node:
                dfs(nr, nc, node)
        grid[r][c] = ch                   # restore
        if not node:                      # prune exhausted branch
            parent.pop(ch)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] in root:
                dfs(r, c, root)
    return found

Complexity

TimeO(m · n · 3^L)
SpaceO(total characters)

Each of the m × n cells can start a search up to depth L (the longest word) with at most 3 new directions per step. Shared prefixes are explored once for all words, and pruning removes finished branches. The trie stores every word's characters.

Common mistakes

Frequently asked questions

What is the time and space complexity of Word Search II?

Roughly O(m × n × 3^L) time, where L is the longest word, independent of how many words share prefixes. The trie uses O(total characters of all words) space and the recursion O(L).

Why is a trie better than running Word Search for each word?

Words that share a prefix share trie nodes, so a single DFS explores that prefix once for all of them, and it stops as soon as the path is not a prefix of any remaining word.

What does pruning the trie do?

After a word is found and its branch has no other words left, removing that branch means later searches stop earlier. On large inputs this is often the difference between passing and timing out.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Design & Tries LRU Cache (HashMap + Linked List) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.