Word Search

▶

Steps

setup

Initialize board dimensions and directions

The algorithm calculates the number of rows and columns in the board and sets up the directions array for exploring neighbors (down, up, right, left).

💡 Knowing the board size and directions upfront allows the DFS to navigate the grid systematically.

Line:

rows, cols = len(board), len(board[0])
directions = [(1,0), (-1,0), (0,1), (0,-1)]

💡 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.

enteringboard="[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]"word="ABCCED"

Call Path (current → root)

exist(board, word)

choosingi=0j=0index=0

Call Path (current → root)

exist(board, word)

Remaining

(0,0)

enteringr=0c=0index=0

Call Path (current → root)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A]

choosingr=0c=0index=0

Call Path (current → root)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A]

pruningr=1c=0index=1

Call Path (current → root)

dfs(1,0,1)

dfs(0,0,0)

exist(board, word)

Partial: [A]

✂ board[1][0] = 'S' != 'B'

pruningr=-1c=0index=1

Call Path (current → root)

dfs(-1,0,1)

dfs(0,0,0)

exist(board, word)

Partial: [A]

✂ out of bounds

enteringr=0c=1index=1

Call Path (current → root)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A, B]

choosingr=0c=1index=1

Call Path (current → root)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A, B]

pruningr=1c=1index=2

Call Path (current → root)

dfs(1,1,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Partial: [A, B]

✂ board[1][1] = 'F' != 'C'

pruningr=-1c=1index=2

Call Path (current → root)

dfs(-1,1,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Partial: [A, B]

✂ out of bounds

enteringr=0c=2index=2

Call Path (current → root)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A, B, C]

choosingr=0c=2index=2

Call Path (current → root)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A, B, C]

enteringr=1c=2index=3

Call Path (current → root)

dfs(1,2,3)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A, B, C, C]

choosingr=1c=2index=3

Call Path (current → root)

dfs(1,2,3)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A, B, C, C]

enteringr=2c=2index=4

Call Path (current → root)

dfs(2,2,4)

dfs(1,2,3)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A, B, C, C, E]

choosingr=2c=2index=4

Call Path (current → root)

dfs(2,2,4)

dfs(1,2,3)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Remaining

downuprightleft

Partial: [A, B, C, C, E]

pruningr=3c=2index=5

Call Path (current → root)

dfs(3,2,5)

dfs(2,2,4)

dfs(1,2,3)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Partial: [A, B, C, C, E]

✂ out of bounds

pruningr=1c=2index=5

Call Path (current → root)

dfs(1,2,5)

dfs(2,2,4)

dfs(1,2,3)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Partial: [A, B, C, C, E]

✂ visited cell

pruningr=2c=3index=5

Call Path (current → root)

dfs(2,3,5)

dfs(2,2,4)

dfs(1,2,3)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Partial: [A, B, C, C, E]

✂ board[2][3] = 'E' != 'D'

backtrackingr=2c=1index=5

Call Path (current → root)

dfs(2,1,5)

dfs(2,2,4)

dfs(1,2,3)

dfs(0,2,2)

dfs(0,1,1)

dfs(0,0,0)

exist(board, word)

Partial: [A, B, C, C, E, D]

Found 1: [ABCCED]

Key Takeaways

✓ 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. 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

1. Step 1: Understand problem requirements

   The problem requires generating all palindrome partitions, not just counting or finding one.

2. Step 2: Identify suitable algorithm

   Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. 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

2. Given the following code for generating unique permutations, what is the final output when the input is [1,1,2]?

from typing import List

def permuteUnique(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        seen = set()
        for i in range(start, len(nums)):
            if nums[i] in seen:
                continue
            seen.add(nums[i])
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

print(permuteUnique([1,1,2]))

easy

A. [[1,2,1],[1,1,2],[2,1,1]]

B. [[1,1,2],[2,1,1],[1,2,1]]

C. [[1,1,2],[1,2,1],[2,1,1]]

D. [[2,1,1],[1,1,2],[1,2,1]]

Solution

1. Step 1: Trace initial sorting and first level of recursion

   Input sorted to [1,1,2]. At start=0, i iterates over 0 to 2. First, swap nums[0] with nums[0] (1), add 1 to seen, recurse.

2. Step 2: Trace subsequent recursion and skipping duplicates

   At start=1, i iterates 1 to 2. Swap nums[1] with nums[1] (1), add 1 to seen, recurse. Then swap nums[2] with nums[1] (2), add 2 to seen, recurse. Duplicate 1 at i=2 skipped due to seen.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected unique permutations in lex order [OK]

Hint: Sort input and skip duplicates with seen set [OK]

Common Mistakes:

• Misordering output permutations due to swap order

3. You are given a string containing only digits. Your task is to split it into exactly four parts such that each part represents a valid IP address segment (0 to 255, no leading zeros except for '0'). Which algorithmic approach guarantees finding all valid IP addresses efficiently?

easy

A. Sorting the digits and then partitioning into four segments

B. Greedy approach that picks the shortest valid segment at each step

C. Dynamic programming to count the number of valid segmentations

D. Backtracking with pruning to explore all valid segmentations

Solution

1. Step 1: Understand the problem constraints

   The problem requires enumerating all valid IP addresses, which involves exploring multiple segmentations of the string.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they may miss valid segmentations; DP counting does not generate all solutions; sorting digits destroys original order. Backtracking with pruning systematically explores all valid partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking explores all partitions with pruning to avoid invalid segments [OK]

Hint: Backtracking explores all segmentations with pruning [OK]

Common Mistakes:

• Assuming greedy can find all valid IPs
• Using DP counting without generating solutions

4. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

Solution

1. Step 1: Identify how results are stored

   The code appends nums directly to res without copying.

2. Step 2: Understand consequences of appending references

   Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy nums[:] fixes the bug [OK]

Hint: Always append a copy of mutable lists to results [OK]

Common Mistakes:

• Forgetting to copy before appending results in duplicate references

5. Consider the following buggy code snippet for restoring IP addresses. Which line contains the subtle bug that causes invalid IP addresses to be included?

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    stack = [(0, [])]
    while stack:
        start, path = stack.pop()
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            continue
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            continue
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            # Bug: Missing check for leading zeros
            if length == 3 and int(segment) > 255:
                continue
            stack.append((start + length, path + [segment]))
    return res

medium

A. Line missing check for segments with leading zeros

B. Line checking if segment length is 3 and value > 255

C. Line pruning based on remaining characters and segments

D. Line appending new segment to stack

Solution

1. Step 1: Identify missing validation

   The code lacks a check to reject segments with leading zeros like '00' or '01', which are invalid.

2. Step 2: Confirm other checks are correct

   Check for segment > 255 and pruning are present and correct; appending to stack is correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check allows invalid IP segments [OK]

Hint: Leading zero check is mandatory to avoid invalid IPs [OK]

Common Mistakes:

• Forgetting leading zero validation
• Misplacing pruning conditions