Word Search
MediumBacktracking
You are given a grid of letters board and a string word. Return True if word can be spelled by a path through the grid, and False otherwise.
A path:
- starts on any cell whose letter matches the first character of
word, - moves each step to a cell directly above, below, left, or right of the current one (no diagonal moves),
- uses each cell at most once.
The letters along the path, in order, must equal word exactly. Letters are case-sensitive ("a" does not match "A"). You may modify board while searching, as long as your answer is correct.
Example 1
- Input:
- board = [["C","A","T"],["O","R","S"],["W","E","D"]], word = "CORE"
- Output:
- True
- Explanation
- Start at
Cin the top-left, step down toO, right toR, then down toE. Every step is to a horizontal or vertical neighbor, so the word is found.
Example 2
- Input:
- board = [["C","A","T"],["O","R","S"],["W","E","D"]], word = "RAR"
- Output:
- False
- Explanation
Ris next toA, but the board has only oneR, and the path would have to step back onto the cell it already used.
Example 3
- Input:
- board = [["C","A","T"],["O","R","S"],["W","E","D"]], word = "CRED"
- Output:
- False
- Explanation
- The only
RtouchesCdiagonally, and diagonal steps are not allowed, so the path cannot get fromCtoR.
Constraints
m == board.length,n == board[i].length1 <= m, n <= 61 <= word.length <= 15boardandwordcontain only uppercase and lowercase English letters