Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
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.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: The word "ABCCED" can be found starting from the top-left 'A', going right to 'B', 'C', then down to 'C', 'E', and left to 'D'.
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: The word "SEE" can be found starting from board[1][3] = 'S', going down to 'E', then left to 'E'.
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: The word "ABCB" cannot be formed because the 'B' at board[0][1] would need to be reused.
Examples
Example 1
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: The path A→B→C→C→E→D traces through adjacent cells without reusing any cell.
Example 2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: Starting from S at position (1,3), moving down to E at (2,3), then left to E at (2,2).
Example 3
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: Cannot form ABCB because the B at (0,1) would need to be visited twice.
Constraints
- -m == board.length
- -n == board[i].length
- -1 <= m, n <= 6
- -1 <= word.length <= 15
- -board and word consist of only lowercase and uppercase English letters
Optimal Complexity
Time
O(m * n * 4^L)
Space
O(L)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview