Skip to content

Hidden Words in the Grid

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 2 (Click for link to problem statements)

Hidden Words in the Grid

A word-search puzzle is a grid board of letters, plus a list words to look for. A word is present if its letters are laid out in sequentially adjacent cells (up, down, left, right), never reusing a cell within one word.

Return all words from words that appear in the board, in any order.

def find_words(board, words):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 35-45 mins
  • 🛠️ Topics: Backtracking, Depth-First Search (DFS), Trie, Matrix Traversal

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: Which cells count as "adjacent"?
    • A: Only the four cells directly up, down, left, or right of the current cell. Diagonal neighbors do not count.
  • Q: Can a single word use the same board cell more than once?
    • A: No. Each cell may be used at most once per word, but different words are searched independently and may reuse the same cells.
  • Q: Does the order of the returned list matter, and can a word appear twice?
    • A: The words may be returned in any order, and each found word should appear exactly once in the result even if it can be traced along multiple paths.
HAPPY CASE
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']
Explanation: "oath" is traced o(0,0) -> a(0,1) -> t(1,1) -> h(2,1) and "eat" is traced e(1,3) -> a(1,2) -> t(1,1). There is no "p" on the board for "pea", and no letter "a" is adjacent to any "r" for "rain".

EDGE CASE
Input: board = [["a", "b"]], words = ["aba"]
Output: []
Explanation: Spelling "aba" would require returning to the cell (0,0) that was already used for the first "a". A cell cannot be reused within one word, so no words are found.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Matrix Search Problems, we can consider the following approaches:

  • Backtracking with DFS: Explore paths of adjacent cells from each starting cell, marking cells as used on the way down and un-marking them on the way back up. This is the standard pattern for single-word search (Word Search).
  • Trie (Prefix Tree): Because we are searching for many words at once, storing all the words in a trie lets one DFS walk match every word simultaneously and abandon a path the moment no word starts with the letters seen so far.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Insert every word into a trie. Then start a DFS from each cell of the board, walking the board and the trie in lockstep: a step to an adjacent cell is only allowed if that cell's letter is a child of the current trie node. Whenever the DFS reaches a trie node that marks the end of a word, add that word to the results. Mark cells as visited during a path and restore them when backtracking.

1) Build a trie from `words`. At the node where a word ends, store the word itself.
2) For each cell (row, col) in the board, start a DFS with the trie root:
   a) Let char = board[row][col]. If char is not a child of the current trie node, stop (prune).
   b) Move to the child node. If it stores a completed word, append the word to the
      results and remove the marker so the word is only reported once.
   c) Temporarily mark the cell as used (e.g., replace its letter with "#").
   d) Recurse into each in-bounds, unused neighbor (up, down, left, right).
   e) Restore the cell's letter (backtrack).
3) Return the list of found words.

⚠️ Common Mistakes

  • Forgetting to restore a cell after the recursive calls return, which wrongly blocks other paths and other starting cells.
  • Marking a cell visited after recursing instead of before, allowing the same cell to be reused within one word.
  • Reporting a word once per path instead of once total (not removing the end-of-word marker after the first match).
  • Searching each word with its own full board scan instead of using a trie — correct, but repeats the same prefix work for every word.

4: I-mplement

Implement the code to solve the algorithm.

def find_words(board, words):
    if not board or not board[0] or not words:
        return []

    # Build a trie of all the words
    trie = {}
    for word in words:
        node = trie
        for char in word:
            node = node.setdefault(char, {})
        node["$"] = word  # marks the end of a complete word

    rows, cols = len(board), len(board[0])
    found = []

    def backtrack(row, col, node):
        char = board[row][col]
        if char not in node:
            return
        next_node = node[char]

        # If a complete word ends here, record it (pop so it is only added once)
        word = next_node.pop("$", None)
        if word is not None:
            found.append(word)

        board[row][col] = "#"  # mark this cell as used for the current path
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            r, c = row + dr, col + dc
            if 0 <= r < rows and 0 <= c < cols and board[r][c] != "#":
                backtrack(r, c, next_node)
        board[row][col] = char  # restore the cell (backtrack)

        # Prune: remove exhausted trie branches to skip dead-end searches
        if not next_node:
            node.pop(char)

    for row in range(rows):
        for col in range(cols):
            backtrack(row, col, trie)

    return found

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

    • The trie contains branches for "oath", "pea", "eat", and "rain".
    • Starting DFS at (0,0): "o" -> "a"(0,1) -> "t"(1,1) -> "h"(2,1) reaches the end-of-word marker, so "oath" is added.
    • No cell contains "p", so every DFS prunes the "pea" branch immediately at the root.
    • Starting DFS at (1,3): "e" -> "a"(1,2) -> "t"(1,1) reaches the end-of-word marker, so "eat" is added.
    • For "rain": the only "r" is at (2,3), and its neighbors are "e"(1,3), "k"(2,2), and "v"(3,3) — no "a" — so the branch is pruned.
    • Output: ['eat', 'oath'] (any order is acceptable)

  • Input: board = "a","b", words = ["aba"]

    • DFS at (0,0): "a" -> "b"(0,1); the only neighbor of (0,1) is (0,0), which is marked "#", so the path dies before the second "a".
    • Output: []

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume R and C are the number of rows and columns in the board, L is the length of the longest word, and S is the total number of letters across all words.

  • Time Complexity: O(S + R * C * 3^(L-1)). Building the trie costs O(S). Each of the R * C starting cells begins a DFS; after the first step, each path can continue in at most 3 directions (it cannot go back the way it came), for up to L steps. Trie pruning makes the practical runtime far smaller.
  • Space Complexity: O(S + L) — O(S) for the trie and O(L) for the recursion stack. Marking visited cells in place on the board avoids an extra visited structure.

Clone this wiki locally