Solution: Backtracking with DFS
def exist(board, word):
"""
Check if word exists in board
Args:
board: 2D list of characters
word: String to search
Returns:
True if word exists, False otherwise
Time: O(M * N * 4^L) where M,N are board dimensions, L is word length
Space: O(L) for recursion stack
"""
if not board or not board[0]:
return False
rows, cols = len(board), len(board[0])
def dfs(r, c, index):
"""
DFS from position (r, c) matching word[index:]
Returns True if remaining word can be matched
"""
# 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] = '#'
# Try all 4 directions
found = (dfs(r + 1, c, index + 1) or # down
dfs(r - 1, c, index + 1) or # up
dfs(r, c + 1, index + 1) or # right
dfs(r, c - 1, index + 1)) # left
# Restore cell (backtrack)
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
# Test
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
print(exist(board, "ABCCED")) # True
print(exist(board, "SEE")) # True
print(exist(board, "ABCB")) # False
Optimized Solution with Early Termination
def exist_optimized(board, word):
"""
Optimized with frequency check and rare character start
"""
if not board or not board[0] or not word:
return False
rows, cols = len(board), len(board[0])
# Optimization 1: Check if word is too long
if len(word) > rows * cols:
return False
# Optimization 2: Character frequency check
from collections import Counter
board_count = Counter(char for row in board for char in row)
word_count = Counter(word)
for char, count in word_count.items():
if board_count[char] < count:
return False
# Optimization 3: Start from rarer character end
if board_count[word[0]] > board_count[word[-1]]:
word = word[::-1]
def dfs(r, c, index):
if index == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[index]):
return False
temp = board[r][c]
board[r][c] = '#'
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))
board[r][c] = temp
return found
for r in range(rows):
for c in range(cols):
if board[r][c] == word[0] and dfs(r, c, 0):
return True
return False
Alternative: Using Visited Set
def exist_with_visited_set(board, word):
"""
Use separate visited set instead of modifying board
Useful if board should remain immutable
"""
rows, cols = len(board), len(board[0])
def dfs(r, c, index, visited):
if index == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
(r, c) in visited or board[r][c] != word[index]):
return False
visited.add((r, c))
found = (dfs(r + 1, c, index + 1, visited) or
dfs(r - 1, c, index + 1, visited) or
dfs(r, c + 1, index + 1, visited) or
dfs(r, c - 1, index + 1, visited))
visited.remove((r, c))
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0, set()):
return True
return False
Word Search II: Multiple Words with Trie
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def find_words(board, words):
"""
Find all words from list that exist in board
Uses Trie to avoid redundant DFS
Time: O(M * N * 4^L) but with Trie pruning
"""
# Build Trie
root = TrieNode()
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.word = word
rows, cols = len(board), len(board[0])
result = []
def dfs(r, c, node):
char = board[r][c]
if char not in node.children:
return
node = node.children[char]
if node.word:
result.append(node.word)
node.word = None # Avoid duplicates
board[r][c] = '#'
for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
dfs(nr, nc, node)
board[r][c] = char
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return result
Complexity Analysis
- Time Complexity: O(M * N * 4^L)
- Try each of M*N cells as starting point
- Each DFS explores 4 directions, L levels deep
- Optimizations greatly reduce practical runtime
- Space Complexity: O(L)
- Recursion stack depth is word length
- If using visited set: O(L) for set
Key Takeaways
- Backtracking is perfect for "find path" problems
- Mark visited, explore, then unmark (backtrack)
- Early termination optimizations matter for large inputs
- For multiple words, use Trie to share search work
- Space-time tradeoff: modify board vs separate visited set
Related Problems
