💡 The directions array encodes all possible moves from any cell, enabling concise neighbor exploration.
traverse
Start scanning board for first character 'A'
The algorithm begins scanning the board cells row by row, column by column, looking for cells that match the first character 'A' of the word.
💡 Starting DFS only from matching first characters reduces unnecessary searches.
Line:for i in range(rows):
for j in range(cols):
if board[i][j] == word[0]:
💡 Only cells with 'A' can start a valid path for the word.
traverse
First DFS call at cell (0,0) matching 'A'
DFS is called at cell (0,0) because it matches the first character 'A'. The algorithm checks if the current cell matches the word at index 0.
💡 This is the first recursive call exploring a potential path for the word.
Line:if dfs(i, j, 0):
💡 DFS explores paths starting from the first matching cell.
insert
Mark cell (0,0) as visited
The algorithm marks cell (0,0) as visited by replacing 'A' with '#' to avoid revisiting it in this path.
💡 Marking visited cells prevents cycles and repeated use of the same cell.
Line:temp = board[r][c]
board[r][c] = '#'
💡 In-place marking is an efficient way to track visited cells without extra memory.
compare
Explore neighbor down (1,0) for 'B'
DFS tries moving down to cell (1,0) to match the next character 'B' at index 1. The cell contains 'S', which does not match.
💡 Checking neighbors one by one helps find the correct path or prune wrong ones.
Line:for dr, dc in directions:
if dfs(r + dr, c + dc, index + 1):
💡 Mismatch causes pruning and backtracking to try other directions.
compare
Explore neighbor up (-1,0) out of bounds
DFS tries moving up to cell (-1,0), which is outside the board boundaries, so this path is pruned.
💡 Boundary checks prevent invalid memory access and invalid paths.
Line:if r < 0 or r >= rows or c < 0 or c >= cols:
💡 Out-of-bound moves are immediately discarded.
compare
Explore neighbor right (0,1) matching 'B'
DFS moves right to cell (0,1) which contains 'B', matching the next character in the word at index 1. This path is promising and DFS recurses here.
💡 Finding a matching neighbor advances the search deeper.
Line:if dfs(r + dr, c + dc, index + 1):
💡 Matching neighbors extend the current path towards the solution.
insert
Mark cell (0,1) as visited
The algorithm marks cell (0,1) as visited by replacing 'B' with '#' to avoid revisiting it in this path.
💡 Marking visited cells prevents cycles and repeated use of the same cell.
Line:temp = board[r][c]
board[r][c] = '#'
💡 In-place marking is an efficient way to track visited cells without extra memory.
compare
Explore neighbor down (1,1) matching 'C'
DFS moves down to cell (1,1) which contains 'F', not matching 'C' at index 2, so this path is pruned.
💡 Checking neighbors one by one helps find the correct path or prune wrong ones.
Line:for dr, dc in directions:
if dfs(r + dr, c + dc, index + 1):
💡 Mismatch causes pruning and backtracking to try other directions.
compare
Explore neighbor up (-1,1) out of bounds
DFS tries moving up to cell (-1,1), which is outside the board boundaries, so this path is pruned.
💡 Boundary checks prevent invalid memory access and invalid paths.
Line:if r < 0 or r >= rows or c < 0 or c >= cols:
💡 Out-of-bound moves are immediately discarded.
compare
Explore neighbor right (0,2) matching 'C'
DFS moves right to cell (0,2) which contains 'C', matching the next character in the word at index 2. DFS recurses here.
💡 Finding a matching neighbor advances the search deeper.
Line:if dfs(r + dr, c + dc, index + 1):
💡 Matching neighbors extend the current path towards the solution.
insert
Mark cell (0,2) as visited
The algorithm marks cell (0,2) as visited by replacing 'C' with '#' to avoid revisiting it in this path.
💡 Marking visited cells prevents cycles and repeated use of the same cell.
Line:temp = board[r][c]
board[r][c] = '#'
💡 In-place marking is an efficient way to track visited cells without extra memory.
compare
Explore neighbor down (1,2) matching 'C'
DFS moves down to cell (1,2) which contains 'C', matching the next character in the word at index 3. DFS recurses here.
💡 Finding a matching neighbor advances the search deeper.
Line:if dfs(r + dr, c + dc, index + 1):
💡 Matching neighbors extend the current path towards the solution.
insert
Mark cell (1,2) as visited
The algorithm marks cell (1,2) as visited by replacing 'C' with '#' to avoid revisiting it in this path.
💡 Marking visited cells prevents cycles and repeated use of the same cell.
Line:temp = board[r][c]
board[r][c] = '#'
💡 In-place marking is an efficient way to track visited cells without extra memory.
compare
Explore neighbor down (2,2) matching 'E'
DFS moves down to cell (2,2) which contains 'E', matching the next character in the word at index 4. DFS recurses here.
💡 Finding a matching neighbor advances the search deeper.
Line:if dfs(r + dr, c + dc, index + 1):
💡 Matching neighbors extend the current path towards the solution.
insert
Mark cell (2,2) as visited
The algorithm marks cell (2,2) as visited by replacing 'E' with '#' to avoid revisiting it in this path.
💡 Marking visited cells prevents cycles and repeated use of the same cell.
Line:temp = board[r][c]
board[r][c] = '#'
💡 In-place marking is an efficient way to track visited cells without extra memory.
compare
Explore neighbor down (3,2) out of bounds
DFS tries moving down to cell (3,2), which is outside the board boundaries, so this path is pruned.
💡 Boundary checks prevent invalid memory access and invalid paths.
Line:if r < 0 or r >= rows or c < 0 or c >= cols:
💡 Out-of-bound moves are immediately discarded.
compare
Explore neighbor up (1,2) visited cell
DFS tries moving up to cell (1,2), but it is marked as visited ('#'), so this path is pruned.
💡 Visited cells cannot be reused in the current path to avoid cycles.
Line:if board[r][c] != word[index]:
💡 Visited cells are effectively blocked to prevent loops.
compare
Explore neighbor right (2,3) matching 'D'
DFS moves right to cell (2,3) which contains 'E', not matching 'D' at index 5, so this path is pruned.
💡 Checking neighbors one by one helps find the correct path or prune wrong ones.
Line:for dr, dc in directions:
if dfs(r + dr, c + dc, index + 1):
💡 Mismatch causes pruning and backtracking to try other directions.
compare
Explore neighbor left (2,1) matching 'D' and complete word
DFS moves left to cell (2,1) which contains 'D', matching the last character in the word at index 5. Since index + 1 equals word length, the word is found and DFS returns true.
💡 Finding the last character completes the search successfully.
Line:if index == len(word):
return True
💡 The base case confirms the word exists in the board.
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0]) # STEP 1
directions = [(1,0), (-1,0), (0,1), (0,-1)] # STEP 1
def dfs(r, c, index):
if index == len(word): # STEP 20
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]: # STEPS 5,6,9,10,17,18,19
return False
temp = board[r][c] # STEPS 4,8,12,14,16
board[r][c] = '#'
for dr, dc in directions: # STEPS 5,6,7,9,10,11,13,15,17,18,19,20
if dfs(r + dr, c + dc, index + 1):
board[r][c] = temp
return True
board[r][c] = temp
return False
for i in range(rows): # STEP 2
for j in range(cols):
if board[i][j] == word[0] and dfs(i, j, 0): # STEPS 3
return True
return False
📊
Word Search - Watch the Algorithm Execute, Step by Step
Watching the algorithm step through each recursive call and backtrack reveals how the search space is pruned and how the word is matched incrementally, which is difficult to grasp from code alone.
✓ Backtracking explores all possible paths but prunes early when mismatches or boundaries occur.
This pruning is hard to see in code but clear when watching the recursion tree unfold.
✓ In-place marking of visited cells avoids extra memory and prevents cycles effectively.
Understanding this technique is easier when you see cells change state during recursion.
✓ The recursion tree shows how the algorithm tries neighbors in order and backtracks upon failure.
Seeing the order of exploration clarifies why some paths are abandoned and others succeed.
Practice
(1/5)
1. Consider the following Python code implementing the bitmask backtracking solution for N-Queens II. What is the final return value of totalNQueens(4)?
easy
A. 2
B. 0
C. 1
D. 4
Solution
Step 1: Trace initial call for n=4
Start with row=0, no columns or diagonals occupied, all 4 columns available.
Step 2: Count valid placements recursively
Backtracking explores all valid queen placements; for n=4, there are exactly 2 distinct solutions.
Final Answer:
Option A -> Option A
Quick Check:
Known result for 4-queens is 2 solutions [OK]
Hint: 4-queens has 2 solutions; bitmask backtracking counts all [OK]
Common Mistakes:
Off-by-one counting
Confusing number of solutions with board size
2. You need to partition a string into substrings such that every substring is a palindrome. Which algorithmic approach guarantees finding all possible palindrome partitions efficiently by pruning invalid partitions early?
easy
A. Backtracking that explores all substring partitions and checks palindrome validity dynamically
B. Dynamic programming that counts the number of palindromic substrings without generating partitions
C. Greedy approach that picks the longest palindrome substring at each step
D. Breadth-first search that generates partitions level by level without palindrome checks
Solution
Step 1: Understand problem requirements
The problem requires generating all palindrome partitions, not just counting or finding one.
Step 2: Identify suitable algorithm
Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.
Final Answer:
Option A -> Option A
Quick Check:
Backtracking with palindrome checks finds all partitions [OK]
Hint: Backtracking explores all partitions with palindrome pruning [OK]
Common Mistakes:
Assuming greedy longest palindrome picks all partitions
Confusing counting palindromes with generating partitions
Ignoring palindrome checks in BFS
3. You are given a partially filled 9x9 grid where each row, column, and 3x3 sub-box must contain digits 1 through 9 without repetition. Which algorithmic approach guarantees finding a valid solution if one exists?
easy
A. Greedy algorithm that fills cells with the first valid digit found
B. Breadth-first search exploring all possible digit placements simultaneously
C. Dynamic programming by storing subproblems of partially filled grids
D. Backtracking with constraint propagation and heuristic ordering of empty cells
Solution
Step 1: Understand problem constraints
The problem requires filling cells respecting row, column, and box constraints, which is a classic constraint satisfaction problem.
Step 2: Identify algorithm that guarantees solution
Backtracking with constraint propagation prunes invalid choices early, and heuristic ordering reduces branching, ensuring completeness and efficiency.
Final Answer:
Option D -> Option D
Quick Check:
Constraint propagation + heuristic ordering is standard for Sudoku solvers [OK]
Hint: Constraint satisfaction problems need backtracking with pruning [OK]
Common Mistakes:
Assuming greedy or BFS alone can solve Sudoku efficiently
4. What is the time complexity of the optimal backtracking with Trie approach for Word Search II, given a board of size MxN and a list of words with maximum length L? Assume the Trie is already built.
medium
A. O(M * N * 4 * 3^(L-1)) due to pruning and adjacency constraints
B. O(M * N * 4^L * W), where W is the number of words
C. O(M * N * L^2) because each cell explores all prefixes
D. O(M * N * L) since each cell is visited once per character
Solution
Step 1: Identify branching factor in backtracking
From each cell, up to 4 directions are possible initially, then up to 3 directions for subsequent steps due to no revisiting.
Step 2: Calculate complexity with pruning
Trie pruning reduces unnecessary paths, so complexity is roughly O(M * N * 4 * 3^(L-1)) where L is max word length.
Final Answer:
Option A -> Option A
Quick Check:
Matches known complexity from Trie + backtracking analysis [OK]
Hint: Branching factor reduces after first step due to visited constraints [OK]
Common Mistakes:
Confusing W (number of words) as multiplicative factor in optimal approach.
5. If the problem changes so that numbers can be reused multiple times in the permutation (i.e., repetition allowed), which modification to the algorithm is correct?
hard
A. Use a greedy approach to pick the smallest available number at each step until length n is reached.
B. Use the same factorial-based approach but do not remove numbers from the list after selection.
C. Modify factorial computations to account for repeated elements and use a multiset permutation formula.
D. Generate all permutations with backtracking and stop when the k-th is found, since factorial indexing no longer applies.
Solution
Step 1: Understand repetition impact
Allowing reuse breaks the factorial number system assumption because permutations count changes drastically.
Step 2: Identify correct approach
Backtracking with early stop can generate permutations with repetition and find the k-th one, as direct factorial indexing is invalid.
Final Answer:
Option D -> Option D
Quick Check:
Factorial indexing fails with repetition; backtracking is correct fallback [OK]
Hint: Factorial indexing requires unique elements; repetition breaks it [OK]
Common Mistakes:
Trying to reuse factorial indexing without adjustment
Ignoring repetition changes permutation count
Assuming greedy works for k-th permutation with repetition
Recommended