79. Word Search
Array, Backtracking, Matrix, AMateList ·Problem Statement
link: https://leetcode.com/problems/word-search/ https://leetcode.cn/problems/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:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],word = "ABCCED"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],word = "SEE"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],word = "ABCB"
Output: false
Solution Approach
Utilizing Depth-First Search (DFS), navigate the grid to find a path that sequentially constructs the given word, backtracking when necessary.
Algorithm
- Start: Identify cells that match the first letter of the word.
- DFS: From each starting cell, explore neighboring cells using DFS, ensuring each matches the next letter and isn’t revisited.
- Backtrack: If no match is found, backtrack to explore alternate paths.
Implement
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(x, y, step):
if step == l:
return True
for dirx, diry in [(0, 1),(0, -1),(1, 0),(-1, 0)]:
curx, cury = x + dirx, y + diry
if 0 <= curx < m and 0 <= cury < n and flag[curx][cury] and board[curx][cury] == word[step]:
flag[curx][cury] = False
if dfs(curx, cury, step + 1):
flag[curx][cury] = True
return True
flag[curx][cury] = True
return False
m, n = len(board), len(board[0])
l = len(word)
flag = [[True] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
flag[i][j] = False
if dfs(i, j, 1):
return True
flag[i][j] = True
return False