{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Word Search – Solution & Complexity

Interview solutions
/
Word Search

Solution Walkthrough

  1. Step 1: Recognize the Pattern

    The key pattern is: DFS backtracks over matching adjacent cells. Identify the state and invariant before coding.

  2. Step 2: Build the Algorithm

    Advance one state transition at a time. Mark or update state before exploring dependent work.

  3. Step 3: Check Edge Cases

    Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

  4. Step 4: Solution and Complexity

    Time: O(mn4^L). Space: O(L).

    def exist(board: list[str], word: str) -> bool:
    rows, cols, used = len(board), len(board[0]), set()
    def search(r, c, index):
        if index == len(word): return True
        if not (0 <= r < rows and 0 <= c < cols) or (r,c) in used or board[r][c] != word[index]: return False
        used.add((r,c))
        found = any(search(r+dr,c+dc,index+1) for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)))
        used.remove((r,c))
        return found
    return any(search(r,c,0) for r in range(rows) for c in range(cols))

FAQ

See also

Practice Word Search online (run code in the browser)Word Search II solution (hard)N-Queens solution (hard)Pacific Atlantic Water Flow solution (medium)Path Sum II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?