Find a word without reusing a cell

A baseline enumerates all simple board paths and compares their strings afterward. Most prefixes cannot match the word, so this generates unnecessary work. Ordinary BFS with a global visited set also does not solve the problem: reaching a cell at one word position or with one used-cell set does not dominate another attempt.

Start a search at each cell matching the first character. Extend only to an in-bounds, unused neighbor matching the next character. Add that neighbor to the path-local visited set; remove it when the branch returns. Stop as soon as path length equals word length. The explicit stack stores each frame's next direction, making the restore step visible and avoiding recursion limits.

stack cells are distinct, spell exactly the consumed word prefix, and equal the visited set. Popping a failed frame must remove precisely its cell. The board itself never changes. Because each extension consumes another character, search terminates after at most L matched cells for word length L.

For V board cells and L>0, a loose bound is O(V × 4^L) time; after the first step at most three directions can extend a path because the immediate predecessor is used, giving O(V × 3^L) up to constant factors. Validation adds O(V). Auxiliary space is O(min(V,L)) for stack/set; no full board copy is made. L>V immediately fails. This remains exponential rather than becoming linear merely by using DFS.

Follow-up 1 — cells may be reused. Predict ABA on AB: it becomes true. Remove the used-cell constraint; state (row,column,word_index) now suffices for memoization because earlier path history no longer limits legal continuations.

Follow-up 2 — find many dictionary words. Carry a trie node rather than one word index. Missing child edges prune all words sharing that impossible prefix; terminal markers emit matches. Still retain path-local cell usage, and deduplicate words reached through multiple board paths. The trie changes prefix work, not the worst-case combinatorial nature of board paths.

Senior depth distinguishes graph visitation from backtracking state and verifies restoration. Lead depth defines query budgets for adversarial repeated-letter boards.

Reference: solution.py (download file, source below); tests cover reuse rejection, alternative branches, unchanged input, diagonal rejection, empties, and a deep iterative path.

"""Find an orthogonal word path without reusing cells or changing the board."""


def word_search(board, word):
    if any(len(row) != (len(board[0]) if board else 0) for row in board):
        raise ValueError("rectangular board required")
    if any(not isinstance(c, str) or len(c) != 1 for row in board for c in row):
        raise ValueError("single-character cells required")
    if not isinstance(word, str):
        raise ValueError("word must be a string")
    if not word:
        return True
    if not board or not board[0] or len(word) > len(board) * len(board[0]):
        return False
    rows, cols = len(board), len(board[0])
    directions = ((1, 0), (0, 1), (-1, 0), (0, -1))
    for row in range(rows):
        for col in range(cols):
            if board[row][col] != word[0]:
                continue
            visited = {(row, col)}
            # Frame: row, col, next direction. Stack depth is matched length.
            stack = [[row, col, 0]]
            while stack:
                if len(stack) == len(word):
                    return True
                r, c, direction = stack[-1]
                if direction == 4:
                    stack.pop()
                    visited.remove((r, c))
                    continue
                stack[-1][2] += 1
                dr, dc = directions[direction]
                neighbor = nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols and neighbor not in visited
                        and board[nr][nc] == word[len(stack)]):
                    visited.add(neighbor)
                    stack.append([nr, nc, 0])
    return False

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/32-word-search -p 'test_*.py'