0

Word search with a word search II follow-up

by Frontier Interview· about 3 hours ago· ⑂ 0 remixes

Question: Word search with a word search II follow-up

Companies: Glean, Amazon, Snowflake, Uber

Difficulty: Hard

Problem statement

Find words on a letter grid by adjacent moves, then extend the solution to finding many words at once efficiently. Reported on 1point3acres' Glean bank; reconstructed in our own words.

Clarify the setup

A grid of letters. A word is found if it can be spelled by a path of cells that are horizontally or vertically adjacent, using each cell at most once in that path.

  • Part 1: exists(board, word) -> bool.
  • Part 2: given a list of many words, return all that appear.

Ask: are diagonals allowed (no, unless stated)? Case-sensitive (assume yes)? Can the board be empty? In part 2, can the word list contain duplicates (return each found word once)?

Approach

Part 1: backtracking DFS. Start from every cell matching word[0]. From a cell at position i of the word, try the four neighbors for word[i + 1]. Mark the current cell as used (overwrite it with a sentinel such as "#") while exploring and restore it on the way back. That avoids a separate visited set and keeps memory at O(len(word)) for the recursion.

Cheap pruning worth mentioning:

  • If the word is longer than the number of cells, or if the board lacks enough copies of some letter (compare letter counts), return False before searching.
  • If the word's last letter is rarer on the board than its first, search the reversed word: fewer starting points, same answer.

Cost: O(R × C × 3^L) in the worst case (four directions for the first step, then at most three, since you cannot go back), with L the word length.

Part 2: one search for all words with a trie. Running part 1 once per word repeats the same exploration for words that share prefixes. Instead:

  1. Insert every word into a trie; store the full word at its end node.
  2. DFS from every cell, walking the trie alongside the board. Stop as soon as the path is not a prefix of any word.
  3. When a node holding a word is reached, record the word and clear it from the node, so it is reported once.
  4. Prune as you return: if a child node has no word and no children left, delete it from its parent. Over time the trie shrinks to the words not yet found, and searches that can no longer lead anywhere stop early. This is what makes the solution fast on big word lists.

Code

from collections import Counter
from typing import Dict, List

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def exists(board: List[List[str]], word: str) -> bool:
    if not word:
        return True
    if not board or not board[0]:
        return False
    rows, cols = len(board), len(board[0])
    if len(word) > rows * cols:
        return False
    have = Counter(ch for row in board for ch in row)
    need = Counter(word)
    if any(have[ch] < n for ch, n in need.items()):
        return False
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]                    # start from the rarer end

    def dfs(r: int, c: int, i: int) -> bool:
        if board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        saved, board[r][c] = board[r][c], "#"
        try:
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                    return True
            return False
        finally:
            board[r][c] = saved              # restore even on early return

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))


class _Node:
    __slots__ = ("children", "word")

    def __init__(self) -> None:
        self.children: Dict[str, "_Node"] = {}
        self.word = ""


def find_words(board: List[List[str]], words: List[str]) -> List[str]:
    if not board or not board[0]:
        return []
    root = _Node()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, _Node())
        node.word = w
    rows, cols = len(board), len(board[0])
    found: List[str] = []

    def dfs(r: int, c: int, parent: _Node) -> None:
        ch = board[r][c]
        node = parent.children.get(ch)
        if node is None:
            return
        if node.word:
            found.append(node.word)
            node.word = ""                    # report once
        board[r][c] = "#"
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node.children:
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node.children and not node.word:
            del parent.children[ch]           # prune the dead branch

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

The recursion depth is at most the length of the longest word (part 2) or the word (part 1). For words longer than about 1,000 letters, Python's recursion limit becomes a concern; an explicit stack fixes it.

Complexity

  • Part 1: O(R × C × 3^L) time worst case, O(L) extra space. The letter-count check is O(R × C + L).
  • Part 2: building the trie is O(total letters). The search is O(R × C × 3^Lmax) in the worst case, but each path is explored once for all words sharing it, and pruning removes finished branches. Space O(total letters) for the trie.
  • Example: a 12×12 board and 30,000 dictionary words. Calling part 1 per word is 30,000 full searches; the trie version explores each board path once for all words that share it, so the work no longer scales with the number of words.

Test cases

def _board():
    return [list("ABCE"), list("SFCS"), list("ADEE")]


def test_exists_examples():
    assert exists(_board(), "ABCCED")
    assert exists(_board(), "SEE")
    assert not exists(_board(), "ABCB")          # would reuse B
    assert exists(_board(), "")
    assert not exists([], "A")


def test_board_is_restored():
    b = _board()
    exists(b, "ABCCED")
    exists(b, "ABCB")
    assert b == _board()


def test_pruning_paths():
    assert not exists(_board(), "Z")                       # letter missing
    assert not exists([["a", "a"]], "aaa")                 # not enough copies
    assert exists([["a", "b"], ["a", "a"]], "aaab")        # searched reversed internally

def test_find_words_example():
    board = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
    got = find_words(board, ["oath", "pea", "eat", "rain", "oat", "oath"])
    assert sorted(got) == ["eat", "oat", "oath"]


def test_find_words_matches_single_word_search():
    import random
    rng = random.Random(8)
    for _ in range(30):
        board = [[rng.choice("abc") for _ in range(4)] for _ in range(4)]
        words = list({"".join(rng.choice("abc") for _ in range(rng.randint(1, 6))) for _ in range(40)})
        expected = sorted(w for w in words if exists([row[:] for row in board], w))
        assert sorted(find_words([row[:] for row in board], words)) == expected

Follow-ups

  1. Boggle scoring. Return the total score of found words by length: the same trie search, adding points instead of collecting words.
  2. Very large dictionaries. A 300,000-word trie in Python dicts uses a lot of memory. Compress it (a DAWG, or a radix tree that stores strings on edges) and filter words that use letters absent from the board before inserting them.
  3. Many boards, one dictionary. Build the trie once and reuse it, but the pruning step mutates it. Copy-on-write or a per-search "found" set keeps the shared trie intact; you lose some pruning benefit.
  4. Parallelism. Different starting cells are independent apart from the shared "found" state and pruning. Split the board's starting cells across workers, each with its own trie copy, then merge results.
  5. Search as a product. For a search company, the same pattern (walk a trie of known terms along an input) appears in query autocomplete and in spotting entity names in documents. Mention that the trie-plus-pruning idea transfers.

Interviewer expectations

Mid-level (L4)

  • Correct backtracking for part 1 with in-place marking and restoring.
  • Handles reuse of cells, empty inputs and boards where the word is absent.
  • States the exponential worst case.

Senior (L5)

  • Part 2 with a trie, words stored at end nodes, de-duplication, and pruning of dead branches, and can explain why pruning matters.
  • Adds cheap early exits (letter counts, starting from the rarer end) in part 1.
  • Tests part 2 against repeated part 1 calls.

Staff (L6+)

  • Discusses memory for big dictionaries (compressed tries), reusing the trie across boards without breaking pruning, and parallel search.
  • Mentions recursion depth limits and an iterative version.
  • Relates the technique to search-product problems such as autocomplete and entity spotting.

Sign in to comment, vote or remix.