🟨 Word Search (#79)
🔗 Problem Link
📋 Problem Statement
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.
💡 Examples
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
🔑 Key Insights & Approach
Core Observation: Use DFS backtracking from each cell. Mark visited cells, explore 4 directions, unmark when backtracking.
Why Backtracking with DFS?
- O(m * n * 4^L) where L = word length
- Mark visited to avoid reuse
- Backtrack to explore all paths
Approaches:
- DFS backtracking with visited marking: O(m * n * 4^L) - optimal
Pattern: "2D Grid DFS Backtracking" pattern.
🐍 Solution: Python
Approach: DFS Backtracking
Time Complexity: O(m * n * 4^L) | Space Complexity: O(L)
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def dfs(r, c, index):
# Found complete word
if index == len(word):
return True
# Out of bounds or character mismatch
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[index]):
return False
# Mark as visited
temp = board[r][c]
board[r][c] = '#'
# Explore 4 directions
found = (dfs(r + 1, c, index + 1) or
dfs(r - 1, c, index + 1) or
dfs(r, c + 1, index + 1) or
dfs(r, c - 1, index + 1))
# Backtrack: restore cell
board[r][c] = temp
return found
# Try starting from each cell
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
🔵 Solution: Golang
Approach: DFS Backtracking
Time Complexity: O(m * n * 4^L) | Space Complexity: O(L)
func exist(board [][]byte, word string) bool {
rows, cols := len(board), len(board[0])
var dfs func(r, c, index int) bool
dfs = func(r, c, index int) bool {
if index == len(word) {
return true
}
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[index] {
return false
}
// Mark visited
temp := board[r][c]
board[r][c] = '#'
// Explore 4 directions
found := dfs(r+1, c, index+1) ||
dfs(r-1, c, index+1) ||
dfs(r, c+1, index+1) ||
dfs(r, c-1, index+1)
// Backtrack
board[r][c] = temp
return found
}
// Try from each cell
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if dfs(r, c, 0) {
return true
}
}
}
return false
}