Word Ladder

▶

Steps

setup

Initialize sets and variables

Initialize beginSet with 'hit', endSet with 'cog', visited set with both, and level counter to 1.

💡 Setting up these sets prepares the algorithm to expand from both ends simultaneously.

Line:

begin_set = {beginWord}
end_set = {endWord}
visited = set([beginWord, endWord])
level = 1

💡 The algorithm starts with minimal frontiers and tracks visited words to avoid revisiting.

traverse

Choose smaller frontier to expand

Compare sizes of beginSet and endSet; both have size 1, so beginSet is chosen to expand.

💡 Expanding the smaller set reduces the number of transformations to check, improving efficiency.

Line:

if len(begin_set) > len(end_set):
    begin_set, end_set = end_set, begin_set

💡 The algorithm dynamically chooses which frontier to expand based on size.

expand

Generate transformations from 'hit'

For each character in 'hit', generate all one-letter transformations and check if they are in endSet or wordSet.

💡 This step explores all possible next words reachable from 'hit' by changing one letter.

Line:

for i in range(len(word)):
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c == word[i]:
            continue
        next_word = word[:i] + c + word[i+1:]

💡 Systematically generating neighbors is key to BFS traversal in word graphs.

insert

Add 'hot' to next level and visited

'hot' is a valid transformation and not visited, so add it to next_level and mark visited.

💡 Adding new words to next_level prepares them for expansion in the next BFS iteration.

Line:

if next_word in word_set and next_word not in visited:
    visited.add(next_word)
    next_level.add(next_word)

💡 Tracking visited prevents cycles and redundant work.

shrink

Finish expanding 'hit', update beginSet and level

All transformations from 'hit' processed; update beginSet to next_level {'hot'} and increment level to 2.

💡 Moving to the next BFS level means exploring words one step further away.

Line:

begin_set = next_level
level += 1

💡 Level counter tracks the number of transformation steps taken.

traverse

Choose smaller frontier to expand (level 2)

beginSet has size 1 ('hot'), endSet size 1 ('cog'); expand beginSet again.

💡 Continuing to expand the smaller frontier keeps the search balanced.

Line:

if len(begin_set) > len(end_set):
    begin_set, end_set = end_set, begin_set

💡 The algorithm maintains efficiency by always expanding the smaller frontier.

expand

Generate transformations from 'hot'

Generate all one-letter transformations from 'hot' and check if any are in endSet or wordSet.

💡 Exploring neighbors of 'hot' expands the search frontier.

Line:

for i in range(len(word)):
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c == word[i]:
            continue
        next_word = word[:i] + c + word[i+1:]

💡 Systematic neighbor generation continues BFS expansion.

insert

Add 'dot' and 'lot' to next level and visited

'dot' and 'lot' are valid transformations, not visited; add both to next_level and mark visited.

💡 Adding multiple neighbors expands the frontier for the next BFS iteration.

Line:

if next_word in word_set and next_word not in visited:
    visited.add(next_word)
    next_level.add(next_word)

💡 Multiple valid transformations increase the search breadth.

shrink

Finish expanding 'hot', update beginSet and level

All transformations from 'hot' processed; update beginSet to {'dot', 'lot'} and increment level to 3.

💡 Moving to the next BFS level explores words two steps away from beginWord.

Line:

begin_set = next_level
level += 1

💡 Level increments correspond to transformation steps.

traverse

Choose smaller frontier to expand (level 3)

beginSet size 2 ('dot','lot'), endSet size 1 ('cog'); swap sets to expand smaller endSet.

💡 Swapping frontiers ensures the smaller set is expanded for efficiency.

Line:

if len(begin_set) > len(end_set):
    begin_set, end_set = end_set, begin_set

💡 Dynamic swapping balances search from both ends.

expand

Generate transformations from 'cog'

Generate all one-letter transformations from 'cog' and check if any are in beginSet or wordSet.

💡 Exploring neighbors of 'cog' from the end side.

Line:

for i in range(len(word)):
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c == word[i]:
            continue
        next_word = word[:i] + c + word[i+1:]

💡 Bidirectional BFS explores from both ends to meet in the middle.

insert

Add 'dog' and 'log' to next level and visited

'dog' and 'log' are valid transformations, not visited; add both to next_level and mark visited.

💡 Expanding the end frontier with new words.

Line:

if next_word in word_set and next_word not in visited:
    visited.add(next_word)
    next_level.add(next_word)

💡 Visited set prevents revisiting words from either frontier.

shrink

Finish expanding 'cog', update endSet and level

All transformations from 'cog' processed; update endSet to {'dog', 'log'} and increment level to 4.

💡 Next BFS iteration will expand these new words from the end side.

Line:

end_set = next_level
level += 1

💡 Level increments track distance from the end word.

traverse

Choose smaller frontier to expand (level 4)

beginSet size 2 ('dot','lot'), endSet size 2 ('dog','log'); expand beginSet.

💡 When equal size, expand beginSet by default.

Line:

if len(begin_set) > len(end_set):
    begin_set, end_set = end_set, begin_set

💡 Balanced expansion continues.

expand

Generate transformations from 'dot'

Generate all one-letter transformations from 'dot' and check if any are in endSet or wordSet.

💡 Exploring neighbors of 'dot' to find connection to endSet.

Line:

for i in range(len(word)):
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c == word[i]:
            continue
        next_word = word[:i] + c + word[i+1:]

💡 Neighbors of 'dot' include 'dog' which is in endSet.

compare

Detect connection between frontiers at 'dog'

'dog' is in endSet, so the shortest path is found; return level + 1 = 5.

💡 Finding a word in the opposite frontier means the shortest path is complete.

Line:

if next_word in end_set:
    return level + 1

💡 Bidirectional BFS finds the shortest path by meeting in the middle.

def word_ladder_bidirectional(beginWord, endWord, wordList):
    word_set = set(wordList)  # STEP 1
    if endWord not in word_set:
        return 0
    begin_set = {beginWord}  # STEP 1
    end_set = {endWord}  # STEP 1
    visited = set([beginWord, endWord])  # STEP 1
    level = 1  # STEP 1

    while begin_set and end_set:  # STEP 2
        if len(begin_set) > len(end_set):  # STEP 2, 6, 10, 14
            begin_set, end_set = end_set, begin_set
        next_level = set()  # STEP 3
        for word in begin_set:  # STEP 3
            for i in range(len(word)):  # STEP 3
                for c in 'abcdefghijklmnopqrstuvwxyz':  # STEP 3
                    if c == word[i]:  # STEP 3
                        continue
                    next_word = word[:i] + c + word[i+1:]  # STEP 3
                    if next_word in end_set:  # STEP 16
                        return level + 1
                    if next_word in word_set and next_word not in visited:  # STEP 4, 8, 12
                        visited.add(next_word)
                        next_level.add(next_word)
        begin_set = next_level  # STEP 5, 9, 13
        level += 1  # STEP 5, 9, 13
    return 0

if __name__ == '__main__':
    begin = "hit"
    end = "cog"
    word_list = ["hot","dot","dog","lot","log","cog"]
    print(word_ladder_bidirectional(begin, end, word_list))

📊

Word Ladder - Watch the Algorithm Execute, Step by Step

Watching each expansion and transformation step reveals how bidirectional BFS efficiently narrows the search space compared to unidirectional BFS.

Visiting: none

hit

cog

hot

dot

dog

lot

log

Queue / Stack

hitcog

Visiting: hit

hit

cog

hot

dot

dog

lot

log

Queue / Stack

hitcog

Visiting: hit

Edge: hit → hot

hit

hot

dot

dog

lot

log

cog

Queue / Stack

hitcog

Visiting: hit

Edge: hit → hot

hit

hot

dot

dog

lot

log

cog

Queue / Stack

coghot

Visiting: none

hit

hot

dot

dog

lot

log

cog

Queue / Stack

coghot

Visiting: hot

hot

dot

dog

lot

log

cog

hit

Queue / Stack

hotcog

Visiting: hot

Edge: hot → dot

hot

dot

dog

lot

log

cog

hit

Queue / Stack

hotcog

Visiting: hot

Edge: hot → lot

hot

dot

lot

dog

log

cog

hit

Queue / Stack

cogdotlot

Visiting: none

hot

dot

lot

dog

log

cog

hit

Queue / Stack

cogdotlot

Visiting: cog

dot

lot

cog

dog

log

hot

hit

Queue / Stack

cogdotlot

Visiting: cog

Edge: cog → dog

cog

dog

log

dot

lot

hot

hit

Queue / Stack

cogdotlot

Visiting: cog

Edge: cog → log

cog

dog

log

dot

lot

hot

hit

Queue / Stack

doglogdotlot

Visiting: none

cog

dog

log

dot

lot

hot

hit

Queue / Stack

doglogdotlot

Visiting: dot

dot

lot

dog

log

hot

cog

hit

Queue / Stack

dotlotdoglog

Visiting: dot

Edge: dot → dog

dot

dog

lot

log

hot

cog

hit

Queue / Stack

dotlotdoglog

Visiting: dot

Edge: dot → dog

dot

dog

lot

log

hot

cog

hit

Queue / Stack

dotlotdoglog

Key Takeaways

✓ Bidirectional BFS reduces search space by expanding from both ends and meeting in the middle.

This is hard to see from code alone because the dynamic swapping and dual frontiers are subtle.

✓ The algorithm always expands the smaller frontier to optimize performance.

Visualizing frontier sizes clarifies why this heuristic improves efficiency.

✓ The search terminates immediately when a word from one frontier appears in the opposite frontier.

Seeing this early stopping in action helps understand the correctness and speed of bidirectional BFS.

Practice

1. You are given a 2D grid of 0s and 1s. For each cell containing 1, you need to find the distance to the nearest 0. Which algorithmic approach guarantees the shortest distance for all cells efficiently?

easy

A. Use a multi-source Breadth-First Search (BFS) starting from all 0s simultaneously.

B. Run a Depth-First Search (DFS) from each 1 to find the nearest 0.

C. Apply a greedy approach updating distances by scanning rows and columns once.

D. Use a brute force approach checking every cell independently for nearest 0.

Solution

1. Step 1: Understand the problem constraints

   We need shortest distances from each 1 to the nearest 0 in a grid, which is a shortest path problem on an unweighted graph.

2. Step 2: Identify the correct algorithm

   Multi-source BFS starting from all 0s simultaneously guarantees shortest distances because BFS explores neighbors in increasing order of distance.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multi-source BFS ensures shortest path in O(m*n) time [OK]

Hint: Shortest path in grid with multiple sources -> multi-source BFS [OK]

Common Mistakes:

• Using DFS which does not guarantee shortest path
• Greedy scanning misses some paths
• Brute force is too slow

2. Consider the following code snippet implementing the optimal BFS approach for the problem. Given the input grid = [[1,0,0],[0,0,0],[0,0,0]], what is the value of max_dist returned by the function?

easy

A. 4

B. 3

C. -1

D. 2

Solution

1. Step 1: Initialize queue with land cell at (0,0) with distance 0.

   Distances start as -1 except land cells set to 0.

2. Step 2: BFS expands to neighbors, updating distances: (0,1)=1, (1,0)=1, then (0,2)=2, (1,1)=2, (2,0)=2, etc.

   The farthest water cell from land is at distance 2.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Max distance found by BFS is 2 [OK]

Hint: Trace BFS layers to find max distance from land [OK]

Common Mistakes:

• Off-by-one in distance increment
• Confusing max_dist initialization
• Returning -1 when land exists

3. You need to find the cheapest route from a source city to a destination city with at most K stops in between. The graph edges represent flights with costs, and you want the minimum total cost under the stop constraint. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic programming using a 2D table indexed by stops and cities without priority queue.

B. A simple DFS with backtracking exploring all paths up to K stops.

C. A greedy algorithm that always picks the cheapest next flight regardless of stops.

D. Dijkstra's algorithm modified to track the number of stops along with cost.

Solution

1. Step 1: Understand the problem constraints

   The problem requires the cheapest path with at most K stops, so we must track both cost and stops.

2. Step 2: Identify suitable algorithm

   Dijkstra's algorithm can be adapted to track stops as a state parameter, ensuring paths exceeding K stops are not considered, guaranteeing optimality efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Modified Dijkstra tracks stops and cost simultaneously [OK]

Hint: Track stops in Dijkstra to enforce constraints [OK]

Common Mistakes:

• Assuming greedy cheapest next flight always works
• Using DFS without pruning leads to TLE
• Ignoring stops count in shortest path

4. You are given a directed acyclic graph with n nodes and a list of edges. You want to find the smallest set of nodes such that starting a traversal from these nodes can reach every other node in the graph. Which approach guarantees finding this minimal set efficiently?

easy

A. Perform BFS from each node and pick the nodes that can reach all others.

B. Identify all nodes with zero in-degree and return them as the minimal set.

C. Identify all nodes with zero in-degree and return them as the minimal set.

D. Use a dynamic programming approach to count paths from each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires the minimal set of vertices from which all nodes are reachable. Nodes with zero in-degree are exactly those that no other node reaches, so they must be included.

2. Step 2: Analyze approaches

   Performing BFS from each node is inefficient. Dynamic programming counting paths is unnecessary. The minimal set is precisely all nodes with zero in-degree.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Minimal set corresponds exactly to zero in-degree nodes [OK]

Hint: Minimal set corresponds exactly to zero in-degree nodes [OK]

Common Mistakes:

• Assuming BFS from each node is efficient
• Confusing zero in-degree nodes with minimal set without justification
• Using DP which is unnecessary here

5. Consider the following Python code implementing the optimal solution for the minimum effort path problem. Given the input heights = [[1,2,2],[3,8,2],[5,3,5]], what is the final returned minimum effort?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace initial steps

   Start at (0,0) with effort 0. From (0,0), neighbors are (1,0) with effort max(0,|1-3|)=2 and (0,1) with effort max(0,|1-2|)=1.

2. Step 2: Explore paths and update efforts

   Heap pops (0,0,1) with effort 1, then explores neighbors updating efforts. The minimal maximum effort path found is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual tracing confirms minimal effort is 2 [OK]

Hint: Trace heap pops and max edge efforts [OK]

Common Mistakes:

• Confusing sum of differences with max difference
• Off-by-one in indices
• Returning effort before reaching target