DSA sheet · Graphs · BFS pattern

Word Ladder

This is a hard problem, but the teacher promises it will feel like a medium one by the end, and she's right. The trick is to see that the words are nodes of a hidden graph. Two words are joined by an edge when they differ in exactly one letter. Once you see that, "the shortest chain of words" is just BFS level counting, the same thing we did in BFS Traversal. She solves it with BFS first, then shows a small optimisation: never change the letter you just changed.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · BFS, trying every letter at every position
• Part B · Small optimisation: skip the index you just changed
• Part C · Revision page

Part 0 · Before starting

What is a graph?

A graph is a set of nodes (dots, also called vertices) joined by edges (lines). An edge says "these two things are directly connected".

• Undirected edge: you can walk both ways, drawn as (a)—(b).
• Directed edge: one way only, drawn as (a)→(b).
• Weighted edge: the edge has a cost written on it, like (a)—5—(b). With no weights, every edge costs 1 step.

In Word Ladder the edges are undirected (if "hot" can become "dot" by one change, "dot" can become "hot" back) and unweighted (every change costs 1 step).

How graphs are usually given, and the adjacency list

Most graph problems hand you the edges in one of three ways:

We usually turn the input into an adjacency list, because BFS and DFS keep asking "who are the neighbours of this node?".

n = 3
edges = [[0, 1], [1, 2]]
adj = [[] for _ in range(n)]
for a, b in edges:
    adj[a].append(b)     # undirected: add both ways
    adj[b].append(a)
print(adj)               # [[1], [0, 2], [1]]

A graph that nobody gives you: the implicit graph

Word Ladder gives no edges at all. You only get words. The edges are hidden in a rule: two words are neighbours when they have the same length and differ in exactly one position. A graph like this is called implicit: we don't build the adjacency list up front, we find each word's neighbours on the fly, while BFS runs.

How do we find the neighbours of a word? Change one position at a time to each of the 26 letters and ask "is this new word in the dictionary?". That's the heart of this problem.

Visited: why we need it

Graphs can have loops: hot → dot → hot → dot … If we don't remember which nodes we've already seen, BFS goes round forever and counts the same word many times. So every graph walk keeps a visited record. With numbered nodes it's a list of booleans visited[i]. Here the nodes are strings, so we can't index a list with them. We need a set or a dictionary. The teacher uses a neat trick that we'll see in Part A: delete the word from the dictionary set once it's used.

Connected components: groups of nodes that can reach each other. If the end word lies in a different group from the begin word, BFS never reaches it, and the answer is 0.

BFS level by level, and why it gives the shortest path

BFS (Breadth First Search) uses a queue (collections.deque: add at the back with append, take from the front with popleft). It visits the start, then all nodes 1 step away, then all nodes 2 steps away, and so on. To know which level we're on, we take size = len(queue) at the start of each round. Exactly those size nodes form the current level.

from collections import deque
adj = [[1, 2], [0, 3], [0], [1]]   # a tiny example graph
start = 0
queue = deque([start])
visited = {start}
level = 0
while queue:
    size = len(queue)              # nodes on this level
    for _ in range(size):
        node = queue.popleft()
        for nb in adj[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    level += 1                     # finished one whole level
print(level)                       # 3 levels: {0}, {1, 2}, {3}

Because BFS finishes every node at distance 1 before touching distance 2, the first time it reaches a node, it has used the fewest possible steps. In an unweighted graph, BFS layers = shortest path. That's exactly what "shortest transformation sequence" asks for.

DFS (Depth First Search) goes deep along one path using recursion or an explicit stack, then backtracks. We don't need it on this page.

Part A · BFS, trying every letter at every position

LeetCode 127 · Hard

1The question in simple words

You get a beginWord, an endWord and a dictionary wordList. You want to turn the begin word into the end word, step by step:

• In each step you change exactly one letter.
• Every word you pass through (after the begin word) must be in the word list.

Return the number of words in the shortest such chain, counting both the begin word and the end word. If there is no way to reach the end word, return 0.

Example 1: begin = "hit", end = "cog", list = ["hot","dot","dog","lot","log","cog"]. One shortest chain is hit → hot → dot → dog → cog: 5 words, so the answer is 5.

Example 2: the same, but "cog" is not in the list. Then the answer is 0, because the last word of the chain must come from the list.

Here's the hidden graph for Example 1. An edge joins two words that differ in one letter:

                (dot)——(dog)
               /  |       |  \
   (hit)——(hot)   |       |   (cog)
               \  |       |  /
                (lot)——(log)

hot–dot and hot–lot differ in the first letter. dot–lot differ in the first letter too. dot–dog and lot–log differ in the last letter. dog–cog and log–cog differ in the first letter. dog–log differ in the first letter.

2What the constraints tell us

• 1 ≤ beginWord.length ≤ 10, and all words have the same length L → each word has at most 10 positions to change. That's tiny.
• 1 ≤ wordList.length ≤ 5000 → N up to 5000 words. Comparing every pair of words (N² = 25 million pairs, each up to 10 letters) is slow. Trying 26 letters at 10 positions per word is only 260 tries per word.
• Only lowercase English letters → each position has exactly 26 choices, a to z.
• beginWord != endWord → the answer is never 1. All words in the list are unique.
• The begin word does not have to be in the list. The end word does (otherwise the answer is 0).
• Rough work: 5000 words × 10 positions × 26 letters × 10 (to build and hash each new word) ≈ 13 million basic steps. That's well under the ~10⁸ limit, so this approach is fast enough.

3Intuition: how to think about it

Think of the word list as a bag of allowed words. You stand on "hit". You look at one letter at a time, try all 26 letters in its place, and check the bag each time. Every word that's in the bag is one step away. Those words are your first ring. From each of them you do the same to get the second ring, and so on.

The ring number where "cog" first shows up is the length of the shortest chain. Growing rings like this is exactly BFS, where every level = one more letter changed.

4Building the logic from her example

Step 1: from "hit", try every letter at every position

• Change position 0 (h): ait, bit, cit, dit, … zit. None of these are in the list.
• Change position 1 (i): hat, hbt, hct, … hot ✓ in the list! Keep going to z anyway: hpt, hqt, … none.
• Change position 2 (t): hia, hib, hic, … none.

So the only neighbour of "hit" is hot.

Step 2: from "hot", do the same

• Position 0: aot, bot, cot, dot ✓, …, lot ✓, …
• While changing position 0 we also make hot itself again (when the letter is h). Should we add it again? No, we've already used it.
• Positions 1 and 2 give nothing new.

So the next level is dot, lot.

How do we mark "already used" for strings?

We can't make a visited list of booleans, because a list is indexed by numbers and our nodes are words. We could keep a separate dictionary or set of seen words. The teacher's simpler idea:

Step 3 onwards

• From dot: position 0 makes hot and lot, but both are already removed. Position 2 gives dog ✓.
• From lot: position 2 gives log ✓.
• From dog: position 0 gives cog ✓ (log was already removed).
• From log: cog and dog are already removed, so nothing new.
• Next level: we pop cog, which is the end word, so we stop.

Counting: what is a "level" here?

Each level is one more changed letter: hit (1) → hot (2) → dot (3) → dog (4) → cog (5). The answer is the level number where we pop the end word. Since we count words, not changes, the begin word itself is already word number 1.

Rule: if the end word isn't in the list → return 0 straight away

We only ever move to words that are in the set. If "cog" isn't in the set, no step can ever produce it as an allowed word. BFS would run through everything and find nothing. So we check this first and return 0 immediately (Example 2).

Detail: put the original letter back

We change the word inside a list of characters, because Python strings can't be edited in place. While trying position 0 of "hit", the list goes hit → ait → … → zit. When the inner loop ends, the list still says "zit"!

Now we want to try position 1 of the real word "hit", not of "zit". So before changing position 0 we save the letter (original = 'h'), and after trying all 26 letters we put it back: chars[i] = original.

Where do we check for the end word?

Right after popping a word: if word == endWord: return level. The word was put in the queue at this level, so level is its chain length.

(You could also check at the moment you push it and return level + 1. That stops one level earlier. Both give the same answer.)

5Approach steps

1. Put wordList into a set. If endWord isn't in it, return 0.
2. Remove the begin word from the set (if it's there), put it in a queue, and set level = 1.
3. While the queue isn't empty: take size = len(queue) and pop exactly that many words.
4. For each popped word: if it's the end word, return level.
5. Otherwise, for every position i: save the letter, try all 26 letters, and whenever the new word is in the set, push it and remove it from the set. Then put the letter back.
6. After the whole level is done, level += 1.
7. If the queue empties without meeting the end word, return 0.

6Code (Python)

from collections import deque
from string import ascii_lowercase

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        word_set = set(wordList)              # allowed words, also our "not visited yet"
        if endWord not in word_set:           # can never land on the end word
            return 0
        word_set.discard(beginWord)           # never come back to the start

        queue = deque([beginWord])
        level = 1                             # beginWord is word number 1

        while queue:
            size = len(queue)                 # words on this level
            for _ in range(size):
                word = queue.popleft()
                if word == endWord:
                    return level

                chars = list(word)
                for i in range(len(chars)):
                    original = chars[i]       # remember the real letter
                    for c in ascii_lowercase: # try a..z at position i
                        chars[i] = c
                        nxt = "".join(chars)
                        if nxt in word_set:
                            queue.append(nxt)
                            word_set.remove(nxt)   # mark visited
                    chars[i] = original       # put it back before the next position
            level += 1

        return 0

7Code line by line

8Dry run

Example 1: begin "hit", end "cog". At the start, set = {hot, dot, dog, lot, log, cog}.

        (dot*)——(dog)
       /                \
(hit*)—(hot*)          (cog)
       \                /
        (lot*)——(log)

        (dot*)——(dog*)
       /                \
(hit*)—(hot*)          (cog*)
       \                /
        (lot*)——(log*)

Example 2 (no "cog" in the list): the very first check sees that "cog" isn't in the set → return 0, with no BFS at all.

9Complexity & remember

• Time O(N · L · 26 · L), often written O(N · L² · 26). Every word enters the queue at most once, because it's removed from the set when it's pushed. That's N words. For each word we try L positions × 26 letters. Each try builds a new string of length L and hashes it to check the set (and removing from the set also hashes), which costs O(L). With N = 5000 and L = 10 that's about 13 million steps.
• Space O(N · L): the set and the queue each hold up to N words of length L.
• The for _ in range(size) loop doesn't add a factor: across all levels it pops each word once, so it's part of the N.

Part B · Small optimisation: skip the index you just changed

1The question

The same problem as Part A. We only want to cut some wasted work.

2What the constraints tell us

The same as Part A. L ≤ 10, so skipping one position out of L saves at most about 10% of the tries. The teacher says this up front: the gain is small, and the big-O stays the same.

3Intuition: why re-trying that position is wasted work

We reached "hot" from "hit" by changing position 1 (i → o). While we were processing "hit", we already tried every letter at position 1: hat, hbt, …, hot, …, hzt. Any of those that were in the list got pushed and removed then.

Now, at "hot", trying position 1 again makes hat, hbt, …, hzt, the exact same 26 words. They've all been checked already. So when we pop "hot", we can skip position 1 and only try positions 0 and 2.

4Building the logic

• Each queue entry must now carry two things: the word and the index we must skip (the position that was changed to create it). In Python a tuple (word, skip) is enough. She builds a small class with word and skip fields because Java has no ready-made pair.
• The begin word wasn't created by any change, so there's nothing to skip. We give it skip = -1, which matches no real position.
• When we find a neighbour by changing position i, we push (nxt, i).
• When we pop (word, skip), the position loop does if i == skip: continue.

5Approach steps (only what changes)

1. The queue starts with (beginWord, -1).
2. Pop (word, skip). If word is the end word, return level.
3. For every position i, except i == skip: try a–z, and push (nxt, i) for each hit.
4. Everything else (set as visited, restoring the letter, levels starting at 1) stays the same.

6Code (Python)

from collections import deque
from string import ascii_lowercase

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        word_set = set(wordList)
        if endWord not in word_set:
            return 0
        word_set.discard(beginWord)

        queue = deque([(beginWord, -1)])      # (word, index we must not change)
        level = 1

        while queue:
            for _ in range(len(queue)):
                word, skip = queue.popleft()
                if word == endWord:
                    return level

                chars = list(word)
                for i in range(len(chars)):
                    if i == skip:             # already fully tried at the parent
                        continue
                    original = chars[i]
                    for c in ascii_lowercase:
                        chars[i] = c
                        nxt = "".join(chars)
                        if nxt in word_set:
                            queue.append((nxt, i))   # remember which index made it
                            word_set.remove(nxt)
                    chars[i] = original
            level += 1

        return 0

7Code line by line (only the new lines)

8Dry run (Example 1, what gets skipped)

9Complexity & remember

• Time O(N · L² · 26), the same big-O as Part A. Only the constant drops a little (L−1 positions instead of L).
• Space O(N · L): each queue entry also stores one small integer.

Part C · Revision page

s = Solution()
print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))  # 5
print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))         # 0
print(s.ladderLength("a", "c", ["a", "b", "c"]))                                 # 2
print(s.ladderLength("hot", "dog", ["hot", "dog"]))                              # 0
print(s.ladderLength("abc", "xyz", ["xbc", "xyc", "xyz"]))                       # 4

Based on this video: Word Ladder | Graph · BFS