Backtracking · 083Medium
Word Search
Given an m x n grid of characters and a string word, return true if the word can be built from sequentially adjacent cells (horizontal or vertical neighbors). The same cell may not be used more than once.
Constraints
- m == board.length, n == board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word consist of English letters.
Examples
exist([["A","B"],["C","D"]], "AB") -> true exist([["A","B"],["C","D"]], "ABD") -> true // A -> B then down to D exist([["A"]], "A") -> true exist([["A"]], "B") -> false // no matching cell exist([["A","B"],["C","D"]], "AD") -> false // A and D are only diagonal exist([["A","A"],["A","A"]], "AAAAA") -> false // longer than the cell count
Edge cases
- A cell cannot be reused within one path.
- Diagonal moves are not allowed.
- A word longer than the cell count is immediately false.
Show the target complexity (spoiler)
- Naive
- Trying every cell sequence without pruning is factorial in the grid size.
- Target
- O(m * n * 4^L) time — DFS from every matching start cell, marking visited cells and restoring them on the way out.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/10-backtracking/083-word-search.js ./practice c 083