""" p39 — Word Search (LeetCode 79, MEDIUM). Implementations: exist — in-place visited sentinel. O(L) extra space. The default. exist_with_set — separate visited set. Doesn't mutate input. exist_brute — naive exhaustive (no early-bound check, kept for comparison). Stress test: small random grids, compared between the three. Run: python3 solution.py """ from __future__ import annotations import random from typing import List DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1)) # -------------------------------------------------------------------------------------- # Default: in-place visited marking. Mutates board temporarily, restores on backtrack. # -------------------------------------------------------------------------------------- def exist(board: List[List[str]], word: str) -> bool: if not board or not board[0] or not word: return False R, C = len(board), len(board[0]) L = len(word) def dfs(r: int, c: int, i: int) -> bool: if i == L: return True # Single-source-of-truth: bounds + character match + visitedness # (the in-place '#' sentinel makes visited cells fail the char-match check). if r < 0 or r >= R or c < 0 or c >= C or board[r][c] != word[i]: return False # choose saved = board[r][c] board[r][c] = '#' # recurse found = ( dfs(r - 1, c, i + 1) or dfs(r + 1, c, i + 1) or dfs(r, c - 1, i + 1) or dfs(r, c + 1, i + 1) ) # un-choose (restore on BOTH paths — short-circuit True and fall-through False) board[r][c] = saved return found for r in range(R): for c in range(C): if board[r][c] == word[0] and dfs(r, c, 0): return True return False # -------------------------------------------------------------------------------------- # Variant: separate visited set. Doesn't touch the input board. # -------------------------------------------------------------------------------------- def exist_with_set(board: List[List[str]], word: str) -> bool: if not board or not board[0] or not word: return False R, C = len(board), len(board[0]) L = len(word) visited: set = set() def dfs(r: int, c: int, i: int) -> bool: if i == L: return True if ( r < 0 or r >= R or c < 0 or c >= C or (r, c) in visited or board[r][c] != word[i] ): return False visited.add((r, c)) found = any(dfs(r + dr, c + dc, i + 1) for dr, dc in DIRS) visited.remove((r, c)) return found for r in range(R): for c in range(C): if board[r][c] == word[0] and dfs(r, c, 0): return True return False # -------------------------------------------------------------------------------------- # Brute oracle: try ALL paths up to length L using a visited tuple. No char prune until # completion. Slow — keep grids tiny in stress. # -------------------------------------------------------------------------------------- def exist_brute(board: List[List[str]], word: str) -> bool: if not board or not board[0] or not word: return False R, C = len(board), len(board[0]) L = len(word) def dfs(r: int, c: int, i: int, visited: frozenset) -> bool: if i == L: return True if r < 0 or r >= R or c < 0 or c >= C: return False if (r, c) in visited: return False if board[r][c] != word[i]: return False v2 = visited | {(r, c)} for dr, dc in DIRS: if dfs(r + dr, c + dc, i + 1, v2): return True return False for r in range(R): for c in range(C): if dfs(r, c, 0, frozenset()): return True return False # -------------------------------------------------------------------------------------- # Tests # -------------------------------------------------------------------------------------- def edge_cases() -> None: board1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]] assert exist([row[:] for row in board1], "ABCCED") is True assert exist([row[:] for row in board1], "SEE") is True assert exist([row[:] for row in board1], "ABCB") is False assert exist_with_set([row[:] for row in board1], "ABCCED") is True assert exist_with_set([row[:] for row in board1], "ABCB") is False # Confirm exist doesn't permanently mutate b = [row[:] for row in board1] exist(b, "ABCCED") assert b == board1, "exist mutated the board permanently" # Single cell assert exist([["A"]], "A") is True assert exist([["A"]], "B") is False assert exist([["A"]], "AA") is False # 1xN row assert exist([["H", "E", "L", "L", "O"]], "HELLO") is True assert exist([["H", "E", "L", "L", "O"]], "OLLEH") is True # walk right-to-left assert exist([["H", "E", "L", "L", "O"]], "HELLOX") is False # extra letter not present # Full revisit needed (should fail) assert exist([["A", "A"]], "AAA") is False # only 2 cells # Word starts at all corners g = [["X", "Y"], ["Z", "W"]] for ch in "XYZW": assert exist([row[:] for row in g], ch) is True # Long loop word g2 = [["A", "B", "C"], ["D", "E", "F"], ["G", "H", "I"]] assert exist([row[:] for row in g2], "AEI") is False # no diagonal assert exist([row[:] for row in g2], "ABEDG") is True or exist([row[:] for row in g2], "ABEDG") is False # Use a known true path: A→B→E→F→I assert exist([row[:] for row in g2], "ABEFI") is True # Empty word — spec-defensive: undefined, but we treat as False (word.length ≥ 1 in LC) assert exist([["A"]], "") is False print("edge_cases: PASS") def stress_test() -> None: rng = random.Random(42) for _ in range(200): R = rng.randint(1, 4) C = rng.randint(1, 4) # Small alphabet → real chance of matches board = [[rng.choice("ABC") for _ in range(C)] for _ in range(R)] L = rng.randint(1, 5) word = "".join(rng.choice("ABC") for _ in range(L)) a = exist([row[:] for row in board], word) b = exist_with_set([row[:] for row in board], word) c = exist_brute([row[:] for row in board], word) assert a == b == c, f"DISAGREE board={board} word={word!r}: exist={a} set={b} brute={c}" print("stress_test: 200 random grids — in-place, set-based, and brute all agree.") if __name__ == "__main__": edge_cases() stress_test() print("ALL TESTS PASSED")