Word Search — Backtracking

Learn how to search for a word in a 2D grid using backtracking. Explore how DFS with visited-cell marking efficiently finds paths through adjacent cells.

Interactive Python lesson with 224 traced steps across 3 test cases.

Python code

def exist(board, word):
    rows = len(board)
    cols = len(board[0])

    def backtrack(r, c, index):
        if index == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[index]:
            return False

        saved = board[r][c]
        board[r][c] = '#'

        found = (backtrack(r + 1, c, index + 1) or
                 backtrack(r - 1, c, index + 1) or
                 backtrack(r, c + 1, index + 1) or
                 backtrack(r, c - 1, index + 1))

        board[r][c] = saved
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

Test cases

Test 1

board = [["A","B","C"],["S","F","C"],["A","D","E"]]
word = "ABC"

64 visible steps

Test 2

board = [["A","B"],["C","D"]]
word = "ACDB"

66 visible steps

Test 3

board = [["A","B"],["C","D"]]
word = "ABCD"

94 visible steps

Loading the interactive TraceCode visualizer…