Boggle Board

Tags

Boggle Board

Category

Graphs

Difficulty

Hard

Problem Statement

Given a 2D board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (horizontally, vertically, or diagonally — 8 directions). Each cell may be used at most once per word. Return the list of found words.

Intuition

Each cell on the board can be the start of a potential word. From any cell, we explore all 8 neighbors recursively, building a string character by character. A naive approach checks each word independently via DFS, but this is wasteful when words share common prefixes. A trie built from the word list allows us to prune entire branches of the search: if the current path does not match any prefix in the trie, we stop immediately.

Approach

  1. Insert all words into a trie.
  2. For each cell (r, c) on the board:
    • Start a DFS with the trie root. Mark (r, c) as visited.
    • At each step, check if the current character exists as a child in the current trie node.
    • If the current trie node marks the end of a word, add that word to the result set.
    • Recurse into all 8 unvisited neighbors whose characters continue a valid trie path.
    • Unmark (r, c) when backtracking.
  3. Return the collected words (deduplicated).

Pseudocode

function boggleBoard(board, words):
    trie = buildTrie(words)
    found = set()
    rows = length(board)
    cols = length(board[0])

    for r from 0 to rows-1:
        for c from 0 to cols-1:
            visited = 2D boolean array, all false
            dfs(board, r, c, trie.root, visited, found)

    return list(found)

function dfs(board, r, c, trieNode, visited, found):
    char = board[r][c]
    if char not in trieNode.children:
        return

    nextNode = trieNode.children[char]
    if nextNode.isWord:
        found.add(nextNode.word)

    visited[r][c] = true
    for (nr, nc) in 8 neighbors of (r, c):
        if inBounds(nr, nc) and not visited[nr][nc]:
            dfs(board, nr, nc, nextNode, visited, found)
    visited[r][c] = false

Time & Space Complexity

MeasureComplexityJustification
TimeO(R * C * 8^L + W * L)RC starting cells, up to 8^L paths of length L (max word length); WL to build trie. Trie pruning makes the practical runtime much better.
SpaceO(W * L + R * C)Trie storage plus the visited matrix

Key Insights

  • The trie is the critical optimization. Without it, each word requires an independent DFS, and common prefixes are re-explored.
  • Using a set for results naturally handles duplicate words (the same word found via different paths).
  • The visited matrix must be per-search-path (backtracking), not global, because different paths through the board may reuse the same cell.
  • An additional optimization: once a word is found, remove its end-of-word marker from the trie to avoid duplicate work.

Edge Cases

  • Empty board or empty word list: return an empty list.
  • Single-character words: each matching cell contributes the word (deduplicated).
  • Word longer than total cells: impossible to form; trie traversal naturally terminates.
  • Board with all identical characters: words like "aaa" are valid if the board is large enough and all cells are 'a'.
  • Overlapping words: e.g., "cat" and "cats" — the trie handles shared prefixes efficiently.

Linked mentions