Word Search
Medium · Backtracking · Array · String · Backtracking · Depth-First Search · Matrix
Problem
You are given an m × n grid of letters, board, and a string word. Return True if word can be traced on the grid, and False if it cannot.
A trace starts on any cell and moves one step at a time to the cell directly above, below, left or right of it — never diagonally. The letters of the cells it visits, in order, must spell word. A cell can be used only once in a trace: when the word needs the same letter again, it has to come from a different cell. Letters are case-sensitive, so "a" does not match "A".
Follow-up: some tests are built so that almost every path nearly matches, such as a board full of A and the word "AAAAAAAAAAAAAAB". A plain search tries millions of paths there. Can you rule such cases out before searching?
Examples
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: True
Start at the top-left A, go right to B and C, down to the C below it, then down to E and left to D.
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: False
After A, B and C, the only B next to that C is the one already used.
Constraints
- m == len(board), n == len(board[i])
- 1 <= m, n <= 6
- 1 <= len(word) <= 15
- board and word contain only English letters, lowercase and uppercase
Approaches
- Plain backtracking, no pruning — time O(m · n · 3^L), space O(L)
Follow-up
Can you prune the search so that it stays fast on larger boards?
Related problems
Start free on Cariara · Coding problems · System design studio
