Backtracking
LC #79Medium
Word Search
Backtracking
AmazonGoogleMetaMicrosoftProblem
Find if a word exists in a 2D board by connecting adjacent (not diagonal) cells.
arraybacktrackingmatrix
Constraints
- ›1 ≤ m, n ≤ 6
- ›1 ≤ word.length ≤ 15
- ›Uppercase English letters only
- ›Each cell can only be used once per path
Example
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"Output
trueWhy
Path: A(0,0)→B(0,1)→C(0,2)→C(1,2)→E(2,2)→D(2,1)