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
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false
Constraints:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board
and word
consists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board
?
The problem asks to determine if a given word exists in a grid of characters. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically), and each cell can be used only once.
This is a classic graph traversal problem that can be solved efficiently using Depth-First Search (DFS) with backtracking.
Approach:
DFS with Backtracking: The core of the solution is a recursive DFS function. It explores all possible paths from a starting point in the grid, checking if they spell out the target word. Crucially, it uses backtracking to undo the changes made to the grid as it explores different branches of the search tree.
Base Cases:
k
in the word
reaches the end (k == word.length - 1
), it checks if the current grid cell matches the last character of the word. If it does, the word is found.word[k]
, the path is invalid, so it returns false
.Recursive Step:
true
, it means the word was found along that path.Iteration over Starting Points: The main function iterates through every cell in the grid, using each as a potential starting point for the DFS search. If the DFS finds the word from any starting point, the function immediately returns true
.
Time Complexity Analysis:
k
). Thus, the worst-case time complexity of the DFS function is O(4k).Space Complexity Analysis:
k
). Therefore, the space complexity is O(k).Code (Python):
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(row, col, index):
if index == len(word):
return True # Word found
if row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != word[index]:
return False # Out of bounds or mismatch
temp = board[row][col] #Store the character
board[row][col] = '#' #Mark as visited
res = (dfs(row + 1, col, index + 1) or
dfs(row - 1, col, index + 1) or
dfs(row, col + 1, index + 1) or
dfs(row, col - 1, index + 1))
board[row][col] = temp #Backtrack: Restore the character
return res
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
The code in other languages (Java, C++, Go, TypeScript, JavaScript, Rust, C#) provided previously follows the same algorithmic approach, differing only in syntax and data structures used. They all efficiently solve the Word Search problem using DFS and backtracking.