Definition
- Implicit graph – each word is a node; an edge connects two words that differ by exactly one letter.
- BFS – breadth-first search from the begin word finds the shortest path because all edges have unit cost.
- On-the-fly neighbours – for each word, try every single-letter substitution (L positions * 26 letters) and keep only dictionary words.
- Hash set dictionary – O(1) membership checks; removing a word from the set when it is enqueued prevents revisiting.
- Bidirectional BFS – searching from both the begin and end words simultaneously can dramatically shrink the explored frontier.
The National Bank of India migrates an old product code to a new one, but compliance forces every intermediate code to be a valid registered code in the catalogue, changing one character at a time. The bank wants the shortest valid chain from the old code to the new one.
Understanding the Concepts
What is the Word Ladder problem?
Given a begin word, an end word, and a dictionary of equal-length words, find the length of the shortest transformation sequence from the begin word to the end word, changing exactly one letter at a time. Every intermediate word must exist in the dictionary. If no such sequence exists, return 0.
package com.bank.migration;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class WordLadder {
public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
dict.remove(beginWord);
int steps = 1;
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
char[] word = queue.poll().toCharArray();
for (int j = 0; j < word.length; j++) {
char original = word[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
word[j] = c;
String next = new String(word);
if (next.equals(endWord)) return steps + 1;
if (dict.remove(next)) {
queue.offer(next);
}
}
word[j] = original;
}
}
steps++;
}
return 0;
}
}
Why does BFS give the shortest chain?
In an unweighted graph where every edge has the same cost, BFS explores nodes level by level, guaranteeing that the first time you reach a node is via the shortest path. Since each single-letter change is one step, BFS from the begin word finds the fewest transformations to reach the end word.
// BFS level by level:
// Level 1: begin word (1 step)
// Level 2: all words 1 change away (2 steps)
// Level 3: all words 2 changes away (3 steps)
// First time end word appears → shortest chain
How are neighbours generated on the fly?
For each word at the front of the queue, try replacing each position with each letter from 'a' to 'z'. For a word of length L, this generates L * 26 candidates. Check each candidate against the dictionary hash set. If it exists, it is a valid neighbour.
package com.bank.migration;
public class NeighbourGenDemo {
public static void demonstrate() {
String word = "hot";
// Position 0: aot, bot, cot, dot, ..., zot
// Position 1: hat, hbt, hct, hdt, ..., hzt
// Position 2: hoa, hob, hoc, ..., hoz
// Total candidates: 3 * 26 = 78
// Keep only those in the dictionary: e.g., "dot", "lot", "hat"
System.out.println("Neighbours of 'hot': check 78 candidates against dictionary");
}
}
Why remove words from the dictionary as a visited marker?
When a word is enqueued, removing it from the dictionary set prevents it from being enqueued again from a different path. This is equivalent to a visited set but avoids maintaining a separate data structure. The dictionary set serves double duty: membership check and visited tracking.
// Without visited tracking:
// "hot" → "dot" (enqueued)
// "lot" → "dot" (enqueued AGAIN!) → wasted work, potentially infinite
// With dict.remove:
// "hot" → "dot" (enqueued, removed from dict)
// "lot" → "dot" (not in dict anymore → skip)
// Clean, efficient, no duplicates
What is bidirectional BFS?
Bidirectional BFS searches from both the begin word and the end word simultaneously, alternating levels. The search meets in the middle, dramatically reducing the explored frontier. If the shortest path has length d, unidirectional BFS explores up to 26^d nodes, while bidirectional explores up to 2 * 26^(d/2), which is exponentially smaller.
package com.bank.migration;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class BidirectionalWordLadder {
public static int ladderLength(String begin, String end, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(end)) return 0;
Set<String> front = new HashSet<>();
Set<String> back = new HashSet<>();
front.add(begin);
back.add(end);
dict.remove(begin);
dict.remove(end);
int steps = 1;
while (!front.isEmpty() && !back.isEmpty()) {
// Always expand the smaller frontier
if (front.size() > back.size()) {
Set<String> temp = front; front = back; back = temp;
}
Set<String> nextFront = new HashSet<>();
for (String word : front) {
char[] arr = word.toCharArray();
for (int j = 0; j < arr.length; j++) {
char orig = arr[j];
for (char c = 'a'; c <= 'z'; c++) {
arr[j] = c;
String next = new String(arr);
if (back.contains(next)) return steps + 1;
if (dict.remove(next)) nextFront.add(next);
}
arr[j] = orig;
}
}
front = nextFront;
steps++;
}
return 0;
}
}
What is the time and space complexity?
| Approach | Time | Space | Notes |
|---|---|---|---|
| Unidirectional BFS | O(N * L * 26) | O(N) | N=dict size, L=word length |
| Bidirectional BFS | O(N * L * 26) worst | O(N) | Much faster in practice |
| Build full graph + BFS | O(N^2 * L) | O(N^2) | Impractical for large N |
What are edge cases?
Edge cases include the end word not in the dictionary (return 0), the begin word equal to the end word (return 1 or 0 depending on the problem definition), a single-letter word (26 possible neighbours), and no valid path existing.
package com.bank.migration;
import java.util.Arrays;
public class EdgeCases {
public static void test() {
// End word not in dictionary
System.out.println(WordLadder.ladderLength("hit", "cog",
Arrays.asList("hot", "dot", "dog", "lot", "log")));
// "cog" not in dict → 0
// Valid path
System.out.println(WordLadder.ladderLength("hit", "cog",
Arrays.asList("hot", "dot", "dog", "lot", "log", "cog")));
// hit→hot→dot→dog→cog = 5
}
}
0
5
What are common mistakes?
The most common mistake is not removing visited words, which leads to infinite loops or exponential duplicate processing. Another mistake is building the full graph explicitly (O(N^2) edges), which wastes time and memory when on-the-fly generation is sufficient.
package com.bank.migration;
public class CommonMistakes {
// WRONG: not removing visited words
// "hot" → "dot" → "hot" → "dot" → ... (infinite loop!)
// Fix: dict.remove(next) when enqueuing
// WRONG: building full graph
// Comparing every pair of words: O(N^2 * L)
// Fix: generate neighbours on the fly: O(L * 26) per word
}
How is this used in banking?
At the National Bank of India, the product team migrates old product codes to new ones. Compliance requires every intermediate code to be a valid registered code in the catalogue, and only one character can change per step. The migration planner loads the catalogue into a hash set and runs BFS to find the shortest compliant chain from the old code to the new one.
package com.bank.migration;
import java.util.Arrays;
import java.util.List;
public class ProductCodeMigration {
public static void main(String[] args) {
String oldCode = "SAV";
String newCode = "LON";
List<String> catalogue = Arrays.asList(
"SAV", "SAL", "SOL", "LOL", "LON", "SON", "SAN");
int steps = WordLadder.ladderLength(oldCode, newCode, catalogue);
if (steps == 0) {
System.out.println("No valid migration path exists.");
} else {
System.out.println("Shortest migration: " + steps + " steps");
}
}
}
Shortest migration: 4 steps
Visual Overview
Word Ladder BFS
================
Begin: "hit" End: "cog"
Dict: {hot, dot, dog, lot, log, cog}
Level 1: ["hit"] steps=1
Generate neighbours of "hit":
h→a..z: ait,bit,...,hot(in dict!),...
i→a..z: hat,hbt,...
t→a..z: hia,hib,...
Enqueue: "hot", remove from dict
Level 2: ["hot"] steps=2
Neighbours: "dot"(dict), "lot"(dict), "hog"(not), ...
Enqueue: "dot", "lot"
Level 3: ["dot", "lot"] steps=3
"dot" → "dog"(dict)
"lot" → "log"(dict)
Enqueue: "dog", "log"
Level 4: ["dog", "log"] steps=4
"dog" → "cog"(end word!) → return 5
Path: hit → hot → dot → dog → cog (5 words, 4 changes)
Bidirectional BFS
==================
Front (from begin): {hit}
Back (from end): {cog}
Expand front: hit → {hot}
Expand back: cog → {dog, log, cog→...}
Expand front: hot → {dot, lot}
Expand back: {dog,log} → {dot(in front!)} → MEET!
Frontier sizes are much smaller → faster
Unidirectional: explores ~26^d nodes
Bidirectional: explores ~2*26^(d/2) nodes
Key Takeaway
Word Ladder is a shortest path problem hiding behind a string puzzle. Each word is a node in an implicit graph, and an edge connects any two words that differ by exactly one letter. Because all edges have unit cost, BFS from the begin word finds the shortest transformation sequence to the end word. Neighbours are generated on the fly by trying every single-letter substitution and checking against the dictionary.
The two implementation details that make this efficient are a hash set for the dictionary (O(1) membership checks) and removing each word from the set when it is enqueued (doubling as a visited marker). Processing the queue level by level and incrementing the step count after each level gives the shortest chain length the first time the end word is reached.
At the National Bank of India, the product team used this for product-code migration where compliance required every intermediate code to be valid in the catalogue and only one character could change per step. They loaded the catalogue into a hash set and ran level-by-level BFS to find the shortest compliant migration path.
For large dictionaries, bidirectional BFS searching from both the begin and end words simultaneously and meeting in the middle dramatically reduces the explored frontier. This is the key optimization that makes the algorithm practical at scale.
Remember one sentence: each word is a node, one-letter changes are edges, BFS gives the shortest chain, and removing words from the dictionary set prevents revisiting.
---