{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Word Search – Solution & Complexity

Interview solutions
/
Word Search

1. Recognize the Pattern

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

2. Build the Algorithm

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

3. Check Edge Cases

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

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)Pacific Atlantic Water Flow solution (medium)Clone Graph solution (medium)Combination Sum solution (medium)Design Add and Search Words solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?