Word Search

Medium· backtracking· grid dfs

Problem

Given a grid of letters and a word, decide whether the word can be traced through the grid. Consecutive letters must be in horizontally or vertically adjacent cells, and no cell may be used twice in one path.

Examples

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Input: same board, word = "ABCB"

Output: false

The path would have to reuse the B cell.

Constraints

• 1 <= rows, cols <= 6
• 1 <= word.length <= 15
• Letters are upper and lower case English

Hints & approach

Hint 1

Try starting a depth-first search from every cell that matches the first letter.

Hint 2

Mark a cell as visited while it is on the current path, and unmark it when you back out.

Hint 3

Prune quickly: return false the moment a cell does not match the next letter.

Approachtry the hints first

For each cell, run a DFS dfs(r, c, i) that checks whether the word from index i can start at (r, c). Fail on out-of-bounds or a letter mismatch; succeed when i reaches the word length. Otherwise temporarily overwrite the cell with a sentinel to mark it used, recurse into the four neighbours with i + 1, and restore the letter afterwards. Restoring on the way out is the backtracking step that lets other paths reuse the cell. Each DFS branches at most three ways after the first step.

Time O(R * C * 3^L), L = word length · Space O(L) recursion

← PreviousPalindrome Partitioning Next →N-Queens