Blind 75 · #38 · Backtracking

Word Search

MediumGrid backtrackingTime O(cells · 3^L)Space O(L)

Word Search is a medium Backtracking problem from the Blind 75. The key pattern is grid backtracking, and a good solution runs in O(cells · 3^L) time.

Problem

Determine whether a word can be traced through horizontally or vertically adjacent cells without reusing a cell.

Examples

Example 1

Input

{"board":[["A","B","C"],["D","E","F"]],"word":"BEF"}

Output

true

Example 2

Input

{"board":[["D","U","E"],["C","O","L"],["R","E","S"]],"word":"DUEL"}

Output

true

Example 3

Input

{"board":[["D","U","E"],["C","O","L"],["R","E","S"]],"word":"CODE"}

Output

false

Approach

Start a depth-first search from each matching cell, step to adjacent cells for the next letter, and undo the visited mark when backing out.

Pattern	Grid backtracking
Time	O(cells · 3^L)
Space	O(L)

Watch out for

A cell can be used only once within a single word.

Word Search

Problem

Examples

Example 1

Example 2

Example 3

Approach

Watch out for

More Backtracking problems