Word Search
The key idea
From each cell that matches the first letter, run a depth-first search that walks to adjacent cells matching the next letter, marking each visited cell so it cannot be reused, and un-marking it (backtracking) when a branch dead-ends.
Problem
Given an m x n grid of characters board and a string word, return true if word exists in the grid, and false otherwise.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Constraints
m == board.lengthn == board[i].length- 1 <=
m,n<= 6 - 1 <=
word.length<= 15 boardandwordconsist of only lowercase and uppercase English letters
Examples
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Complexity
Time: O(m*n*4^L) Space: O(L)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- CombinationsMEDIUM
- Generate ParenthesesMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-QueensHARD
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM