DSA-102 · Generate one-letter graph edges and remove dictionary vertices on discovery

Word Ladder

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 33804 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the fewest words in a sequence transforming begin to end by changing exactly one lowercase letter per step, with every changed-to word in the supplied dictionary. Return zero if impossible.

begin and end are nonnull, nonempty lowercase-ASCII words of equal length L<=20. The nonnull dictionary list has at most 5,000 nonnull lowercase-ASCII entries of that same length; duplicates are allowed. Size bounds are preconditions. Null inputs/entries throw NullPointerException; invalid alphabet, empty begin or length mismatch throws IllegalArgumentException. Validate all entries before any identity/membership shortcut.
begin need not be in the dictionary. If begin.equals(end), return 1 even when absent from the dictionary. Otherwise end must occur in the dictionary. Edges change exactly one position to a different letter; unchanged words are not edges.
Return word count including both endpoints, not number of edits. Preserve the caller list, order and element references, including unmodifiable lists. Duplicate dictionary occurrences represent one vertex, and all traversal removals occur only in a private set.

Examples

Input: hit→cog; [hot,dot,dog,lot,log,cog,cog]
Output: 5
One shortest chain is hit,hot,dot,dog,cog; duplicate cog does not create another level.
Input: same→same; []
Output: 1
The explicitly allowed identity case needs no change or dictionary membership.
Input: aaa→bbb; [aac,bbb]
Output: 0
The target is present but lies outside the reachable one-letter component.

Before you start

Implicit graph neighbors and unweighted BFS distances
String construction/hash costs and set discovery ownership

Recognize the structure

Dictionary words form an implicit unweighted graph. Comparing every pair materializes many potential edges; generating each one-letter candidate on demand lets BFS explore only reachable vertices, while a private unused set provides membership and discovery ownership.

Try before revealing

Hint 1

Treat words as vertices and one-letter changes as unit edges.

Hint 2

Generate candidates instead of comparing every word pair.

Hint 3

BFS from count one, using private-set removal to claim each dictionary word exactly once.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Materialize pairwise Hamming-distance-one edges

Deduplicate the dictionary with insertion-preserving ownership, add begin, compare every word pair, and connect pairs differing in exactly one position. BFS on that explicit graph returns edge distance+1. This compiling baseline makes graph semantics clear but spends O(N²L) pair-comparison work and stores E adjacency occurrences.

Improve the baseline

Validate and handle explicit boundary semantics

After validating the complete list, return one for equal endpoints. Otherwise build a private set, reject a missing end, and remove begin so it cannot be rediscovered.

Generate neighbors by position and replacement letter

For each popped word, copy its characters; at each position try the other 25 letters. Construct the candidate String and restore the original character before moving to the next position.

Remove on successful discovery

Only unused.remove(neighbor)==true schedules a word with parentLength+1. This simultaneously checks dictionary membership and marks discovery. Stop at the first dequeued end, or return zero after exhaustion.

Why it is correct

Implicit edges are exact

Trying one different letter at one position generates every same-length lowercase word at Hamming distance one, and no unchanged or multi-edit word. Dictionary removal admits only legal changed-to vertices.

Unique discovery and shortest distance

Each set member can be removed once, so it has one BFS owner. FIFO expansion means a shorter route would have discovered that vertex from an earlier layer; stored word counts are minimum.

Success and disconnected failure

begin starts with count one. The first target pop therefore gives minimum sequence word count. If the frontier empties first, every dictionary word reachable by valid substitutions was explored and no transformation exists.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private record Step(String word,int length) {}
    private static void letters(String word,int length){Objects.requireNonNull(word,"word");if(word.length()!=length)throw new IllegalArgumentException("different word length");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("invalid letter");}
    private static void validate(String begin,String end,List<String> dictionary){Objects.requireNonNull(begin,"begin");Objects.requireNonNull(end,"end");Objects.requireNonNull(dictionary,"dictionary");if(begin.isEmpty())throw new IllegalArgumentException("empty word");letters(begin,begin.length());letters(end,begin.length());for(String word:dictionary)letters(word,begin.length());}
    public static int ladderLength(String begin,String end,List<String> dictionary) {
        validate(begin,end,dictionary);if(begin.equals(end))return 1;
        Set<String> unused=new HashSet<>(dictionary);if(!unused.contains(end))return 0;
        unused.remove(begin);ArrayDeque<Step> queue=new ArrayDeque<>();queue.addLast(new Step(begin,1));
        while(!queue.isEmpty()) {
            Step step=queue.removeFirst();if(step.word.equals(end))return step.length;
            char[] candidate=step.word.toCharArray();
            for(int position=0;position<candidate.length;position++) {
                char original=candidate[position];
                for(char letter='a';letter<='z';letter++) {
                    if(letter==original)continue;candidate[position]=letter;String neighbor=new String(candidate);
                    if(unused.remove(neighbor))queue.addLast(new Step(neighbor,step.length+1));
                }
                candidate[position]=original;
            }
        }
        return 0;
    }
    private static boolean adjacent(String a,String b){int differences=0;for(int i=0;i<a.length();i++)if(a.charAt(i)!=b.charAt(i)&&++differences>1)return false;return differences==1;}
    public static int baseline(String begin,String end,List<String> dictionary) {
        validate(begin,end,dictionary);if(begin.equals(end))return 1;Set<String> unique=new LinkedHashSet<>(dictionary);if(!unique.contains(end))return 0;unique.add(begin);List<String> words=new ArrayList<>(unique);
        List<List<Integer>> edges=new ArrayList<>();for(int i=0;i<words.size();i++)edges.add(new ArrayList<>());
        for(int i=0;i<words.size();i++)for(int j=0;j<i;j++)if(adjacent(words.get(i),words.get(j))){edges.get(i).add(j);edges.get(j).add(i);}
        int[] distance=new int[words.size()];ArrayDeque<Integer> queue=new ArrayDeque<>();int start=words.indexOf(begin);distance[start]=1;queue.addLast(start);
        while(!queue.isEmpty()){int vertex=queue.removeFirst();if(words.get(vertex).equals(end))return distance[vertex];for(int next:edges.get(vertex))if(distance[next]==0){distance[next]=distance[vertex]+1;queue.addLast(next);}}return 0;
    }
}

Read the meaningful blocks

Restore the candidate position

Without restoration, subsequent positions can accidentally generate multi-edit candidates.

Private set removal preserves inputs

Never remove from or reorder the caller list. Set display order in walkthroughs is logical sorting, not a HashSet iteration guarantee.

String work is not constant per candidate

new String(candidate) copies L characters and its first hash/membership lookup reads characters. Include this cost instead of calling each of 25L candidates O(1).

Complexity

Let K be input dictionary occurrences, N distinct dictionary words plus the possible extra begin vertex, and L word length. Expected main time is O(KL+26NL²): validation/set construction plus up to 25L candidate Strings per expanded vertex, each with O(L) construction/hash work. Early missing/identical cases are cheaper but still validate the full input.

Peak auxiliary storage is O(NL+1), including private membership/frontier references and retained generated word text; cumulative transient candidate allocation is larger than live storage. Baseline expected time is O(KL+N²L+N+E) and auxiliary structure space O(N+E) beyond the given immutable word text. Returned output is one int.

Exact-state walkthroughs

Reveal normal and boundary traces

Discovery removes words once and counts both endpoints

Input: {"begin":"hit","end":"cog","dictionary":["hot","dot","dog","lot","log","cog","cog"]} · Shortest word count / 0: 5

Step 1 of 15: Seed the starting word and remove it from rediscovery.

Distances count words including the start. Removing a dictionary word on discovery gives it one queue owner.

Word ladder — one-letter edges and word-count distance

Phase: seed.

Start: hit. Target: cog.

Input dictionary occurrences — original order

Queue — front at left; lengths count words

hit: 1

Discovered minimum word counts — teaching history

hit: 1

Unused dictionary words — sorted set view

Current word: none. Each discovery changes exactly one character. Duplicate dictionary occurrences share one vertex. Failed candidate lookups are compressed; the Java loop still generates and hashes those Strings. A target return can leave alternatives queued.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
begin	`"hit"`
end	`"cog"`
dictionary	`["hot","dot","dog","lot","log","cog","cog"]`
unused	`["cog","dog","dot","hot","log","lot"]`
queue	`[{"word":"hit","length":1}]`
distance	`[{"word":"hit","length":1}]`
current	`null`
phase	`"seed"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private record Step(String word,int length) {}
 4     private static void letters(String word,int length){Objects.requireNonNull(word,"word");if(word.length()!=length)throw new IllegalArgumentException("different word length");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("invalid letter");}
 5     private static void validate(String begin,String end,List<String> dictionary){Objects.requireNonNull(begin,"begin");Objects.requireNonNull(end,"end");Objects.requireNonNull(dictionary,"dictionary");if(begin.isEmpty())throw new IllegalArgumentException("empty word");letters(begin,begin.length());letters(end,begin.length());for(String word:dictionary)letters(word,begin.length());}
 6     public static int ladderLength(String begin,String end,List<String> dictionary) {
 7         validate(begin,end,dictionary);if(begin.equals(end))return 1;
 8         Set<String> unused=new HashSet<>(dictionary);if(!unused.contains(end))return 0;
 9         unused.remove(begin);ArrayDeque<Step> queue=new ArrayDeque<>();queue.addLast(new Step(begin,1));
10         while(!queue.isEmpty()) {
11             Step step=queue.removeFirst();if(step.word.equals(end))return step.length;
12             char[] candidate=step.word.toCharArray();
13             for(int position=0;position<candidate.length;position++) {
14                 char original=candidate[position];
15                 for(char letter='a';letter<='z';letter++) {
16                     if(letter==original)continue;candidate[position]=letter;String neighbor=new String(candidate);
17                     if(unused.remove(neighbor))queue.addLast(new Step(neighbor,step.length+1));
18                 }
19                 candidate[position]=original;
20             }
21         }
22         return 0;
23     }
24     private static boolean adjacent(String a,String b){int differences=0;for(int i=0;i<a.length();i++)if(a.charAt(i)!=b.charAt(i)&&++differences>1)return false;return differences==1;}
25     public static int baseline(String begin,String end,List<String> dictionary) {
26         validate(begin,end,dictionary);if(begin.equals(end))return 1;Set<String> unique=new LinkedHashSet<>(dictionary);if(!unique.contains(end))return 0;unique.add(begin);List<String> words=new ArrayList<>(unique);
27         List<List<Integer>> edges=new ArrayList<>();for(int i=0;i<words.size();i++)edges.add(new ArrayList<>());
28         for(int i=0;i<words.size();i++)for(int j=0;j<i;j++)if(adjacent(words.get(i),words.get(j))){edges.get(i).add(j);edges.get(j).add(i);}
29         int[] distance=new int[words.size()];ArrayDeque<Integer> queue=new ArrayDeque<>();int start=words.indexOf(begin);distance[start]=1;queue.addLast(start);
30         while(!queue.isEmpty()){int vertex=queue.removeFirst();if(words.get(vertex).equals(end))return distance[vertex];for(int next:edges.get(vertex))if(distance[next]==0){distance[next]=distance[vertex]+1;queue.addLast(next);}}return 0;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the starting word and remove it from rediscovery.
Distances count words including the start. Removing a dictionary word on discovery gives it one queue owner.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","dog","dot","hot","log","lot"]
queue
[{"word":"hit","length":1}]
distance
[{"word":"hit","length":1}]
current
null
phase
"seed"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","dog","dot","hot","log","lot"]
queue
[]
distance
[{"word":"hit","length":1}]
current
{"word":"hit","length":1}
phase
"expand"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","dog","dot","log","lot"]
queue
[{"word":"hot","length":2}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2}]
current
{"word":"hit","length":1}
phase
"discover"
position
1
letter
"o"
neighbor
"hot"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","dog","dot","log","lot"]
queue
[]
distance
[{"word":"hit","length":1},{"word":"hot","length":2}]
current
{"word":"hot","length":2}
phase
"expand"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","dog","log","lot"]
queue
[{"word":"dot","length":3}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3}]
current
{"word":"hot","length":2}
phase
"discover"
position
0
letter
"d"
neighbor
"dot"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","dog","log"]
queue
[{"word":"dot","length":3},{"word":"lot","length":3}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3}]
current
{"word":"hot","length":2}
phase
"discover"
position
0
letter
"l"
neighbor
"lot"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","dog","log"]
queue
[{"word":"lot","length":3}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3}]
current
{"word":"dot","length":3}
phase
"expand"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","log"]
queue
[{"word":"lot","length":3},{"word":"dog","length":4}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3},{"word":"dog","length":4}]
current
{"word":"dot","length":3}
phase
"discover"
position
2
letter
"g"
neighbor
"dog"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog","log"]
queue
[{"word":"dog","length":4}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3},{"word":"dog","length":4}]
current
{"word":"lot","length":3}
phase
"expand"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog"]
queue
[{"word":"dog","length":4},{"word":"log","length":4}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3},{"word":"dog","length":4},{"word":"log","length":4}]
current
{"word":"lot","length":3}
phase
"discover"
position
2
letter
"g"
neighbor
"log"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
["cog"]
queue
[{"word":"log","length":4}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3},{"word":"dog","length":4},{"word":"log","length":4}]
current
{"word":"dog","length":4}
phase
"expand"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
[]
queue
[{"word":"log","length":4},{"word":"cog","length":5}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3},{"word":"dog","length":4},{"word":"log","length":4},{"word":"cog","length":5}]
current
{"word":"dog","length":4}
phase
"discover"
position
0
letter
"c"
neighbor
"cog"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
[]
queue
[{"word":"cog","length":5}]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3},{"word":"dog","length":4},{"word":"log","length":4},{"word":"cog","length":5}]
current
{"word":"log","length":4}
phase
"expand"
Return the first dequeued target’s shortest word count.
FIFO discovery gives minimum edge distance; starting at one converts it to the required number of words. Pending alternatives need not be processed.
begin
"hit"
end
"cog"
dictionary
["hot","dot","dog","lot","log","cog","cog"]
unused
[]
queue
[]
distance
[{"word":"hit","length":1},{"word":"hot","length":2},{"word":"dot","length":3},{"word":"lot","length":3},{"word":"dog","length":4},{"word":"log","length":4},{"word":"cog","length":5}]
current
{"word":"cog","length":5}
phase
"target"
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
5

Validated identical endpoints need one word

Input: {"begin":"same","end":"same","dictionary":[]} · Shortest word count / 0: 1

Step 1 of 2: After full validation, identical words need one word in the ladder.

The identity case is explicit and does not require end in the dictionary. Invalid dictionary data would still be rejected first.

Word ladder — one-letter edges and word-count distance

Phase: same-word.

Start: same. Target: same.

Input dictionary occurrences — original order

Empty.

Queue — front at left; lengths count words

Empty.

Discovered minimum word counts — teaching history

Empty.

Unused dictionary words — sorted set view

Empty.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
begin	`"same"`
end	`"same"`
dictionary	`[]`
unused	`[]`
queue	`[]`
distance	`[]`
current	`null`
phase	`"same-word"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private record Step(String word,int length) {}
 4     private static void letters(String word,int length){Objects.requireNonNull(word,"word");if(word.length()!=length)throw new IllegalArgumentException("different word length");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("invalid letter");}
 5     private static void validate(String begin,String end,List<String> dictionary){Objects.requireNonNull(begin,"begin");Objects.requireNonNull(end,"end");Objects.requireNonNull(dictionary,"dictionary");if(begin.isEmpty())throw new IllegalArgumentException("empty word");letters(begin,begin.length());letters(end,begin.length());for(String word:dictionary)letters(word,begin.length());}
 6     public static int ladderLength(String begin,String end,List<String> dictionary) {
 7         validate(begin,end,dictionary);if(begin.equals(end))return 1;
 8         Set<String> unused=new HashSet<>(dictionary);if(!unused.contains(end))return 0;
 9         unused.remove(begin);ArrayDeque<Step> queue=new ArrayDeque<>();queue.addLast(new Step(begin,1));
10         while(!queue.isEmpty()) {
11             Step step=queue.removeFirst();if(step.word.equals(end))return step.length;
12             char[] candidate=step.word.toCharArray();
13             for(int position=0;position<candidate.length;position++) {
14                 char original=candidate[position];
15                 for(char letter='a';letter<='z';letter++) {
16                     if(letter==original)continue;candidate[position]=letter;String neighbor=new String(candidate);
17                     if(unused.remove(neighbor))queue.addLast(new Step(neighbor,step.length+1));
18                 }
19                 candidate[position]=original;
20             }
21         }
22         return 0;
23     }
24     private static boolean adjacent(String a,String b){int differences=0;for(int i=0;i<a.length();i++)if(a.charAt(i)!=b.charAt(i)&&++differences>1)return false;return differences==1;}
25     public static int baseline(String begin,String end,List<String> dictionary) {
26         validate(begin,end,dictionary);if(begin.equals(end))return 1;Set<String> unique=new LinkedHashSet<>(dictionary);if(!unique.contains(end))return 0;unique.add(begin);List<String> words=new ArrayList<>(unique);
27         List<List<Integer>> edges=new ArrayList<>();for(int i=0;i<words.size();i++)edges.add(new ArrayList<>());
28         for(int i=0;i<words.size();i++)for(int j=0;j<i;j++)if(adjacent(words.get(i),words.get(j))){edges.get(i).add(j);edges.get(j).add(i);}
29         int[] distance=new int[words.size()];ArrayDeque<Integer> queue=new ArrayDeque<>();int start=words.indexOf(begin);distance[start]=1;queue.addLast(start);
30         while(!queue.isEmpty()){int vertex=queue.removeFirst();if(words.get(vertex).equals(end))return distance[vertex];for(int next:edges.get(vertex))if(distance[next]==0){distance[next]=distance[vertex]+1;queue.addLast(next);}}return 0;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

After full validation, identical words need one word in the ladder.
The identity case is explicit and does not require end in the dictionary. Invalid dictionary data would still be rejected first.
begin
"same"
end
"same"
dictionary
[]
unused
[]
queue
[]
distance
[]
current
null
phase
"same-word"
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
1

A missing end stops before BFS

Input: {"begin":"hit","end":"cog","dictionary":["hot","dot"]} · Shortest word count / 0: 0

Step 1 of 2: Reject a missing target before starting BFS.

Every changed-to word must be in the dictionary; only the starting word may be outside it. Sorted set contents are a logical display, not HashSet iteration.

Word ladder — one-letter edges and word-count distance

Phase: missing-end.

Start: hit. Target: cog.

Input dictionary occurrences — original order

Queue — front at left; lengths count words

Empty.

Discovered minimum word counts — teaching history

Empty.

Unused dictionary words — sorted set view

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
begin	`"hit"`
end	`"cog"`
dictionary	`["hot","dot"]`
unused	`["dot","hot"]`
queue	`[]`
distance	`[]`
current	`null`
phase	`"missing-end"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private record Step(String word,int length) {}
 4     private static void letters(String word,int length){Objects.requireNonNull(word,"word");if(word.length()!=length)throw new IllegalArgumentException("different word length");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("invalid letter");}
 5     private static void validate(String begin,String end,List<String> dictionary){Objects.requireNonNull(begin,"begin");Objects.requireNonNull(end,"end");Objects.requireNonNull(dictionary,"dictionary");if(begin.isEmpty())throw new IllegalArgumentException("empty word");letters(begin,begin.length());letters(end,begin.length());for(String word:dictionary)letters(word,begin.length());}
 6     public static int ladderLength(String begin,String end,List<String> dictionary) {
 7         validate(begin,end,dictionary);if(begin.equals(end))return 1;
 8         Set<String> unused=new HashSet<>(dictionary);if(!unused.contains(end))return 0;
 9         unused.remove(begin);ArrayDeque<Step> queue=new ArrayDeque<>();queue.addLast(new Step(begin,1));
10         while(!queue.isEmpty()) {
11             Step step=queue.removeFirst();if(step.word.equals(end))return step.length;
12             char[] candidate=step.word.toCharArray();
13             for(int position=0;position<candidate.length;position++) {
14                 char original=candidate[position];
15                 for(char letter='a';letter<='z';letter++) {
16                     if(letter==original)continue;candidate[position]=letter;String neighbor=new String(candidate);
17                     if(unused.remove(neighbor))queue.addLast(new Step(neighbor,step.length+1));
18                 }
19                 candidate[position]=original;
20             }
21         }
22         return 0;
23     }
24     private static boolean adjacent(String a,String b){int differences=0;for(int i=0;i<a.length();i++)if(a.charAt(i)!=b.charAt(i)&&++differences>1)return false;return differences==1;}
25     public static int baseline(String begin,String end,List<String> dictionary) {
26         validate(begin,end,dictionary);if(begin.equals(end))return 1;Set<String> unique=new LinkedHashSet<>(dictionary);if(!unique.contains(end))return 0;unique.add(begin);List<String> words=new ArrayList<>(unique);
27         List<List<Integer>> edges=new ArrayList<>();for(int i=0;i<words.size();i++)edges.add(new ArrayList<>());
28         for(int i=0;i<words.size();i++)for(int j=0;j<i;j++)if(adjacent(words.get(i),words.get(j))){edges.get(i).add(j);edges.get(j).add(i);}
29         int[] distance=new int[words.size()];ArrayDeque<Integer> queue=new ArrayDeque<>();int start=words.indexOf(begin);distance[start]=1;queue.addLast(start);
30         while(!queue.isEmpty()){int vertex=queue.removeFirst();if(words.get(vertex).equals(end))return distance[vertex];for(int next:edges.get(vertex))if(distance[next]==0){distance[next]=distance[vertex]+1;queue.addLast(next);}}return 0;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Reject a missing target before starting BFS.
Every changed-to word must be in the dictionary; only the starting word may be outside it. Sorted set contents are a logical display, not HashSet iteration.
begin
"hit"
end
"cog"
dictionary
["hot","dot"]
unused
["dot","hot"]
queue
[]
distance
[]
current
null
phase
"missing-end"
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
0

A present target can remain disconnected

Input: {"begin":"aaa","end":"bbb","dictionary":["aac","bbb"]} · Shortest word count / 0: 0

Step 1 of 6: Seed the starting word and remove it from rediscovery.

Distances count words including the start. Removing a dictionary word on discovery gives it one queue owner.

Word ladder — one-letter edges and word-count distance

Phase: seed.

Start: aaa. Target: bbb.

Input dictionary occurrences — original order

Queue — front at left; lengths count words

aaa: 1

Discovered minimum word counts — teaching history

aaa: 1

Unused dictionary words — sorted set view

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
begin	`"aaa"`
end	`"bbb"`
dictionary	`["aac","bbb"]`
unused	`["aac","bbb"]`
queue	`[{"word":"aaa","length":1}]`
distance	`[{"word":"aaa","length":1}]`
current	`null`
phase	`"seed"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private record Step(String word,int length) {}
 4     private static void letters(String word,int length){Objects.requireNonNull(word,"word");if(word.length()!=length)throw new IllegalArgumentException("different word length");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("invalid letter");}
 5     private static void validate(String begin,String end,List<String> dictionary){Objects.requireNonNull(begin,"begin");Objects.requireNonNull(end,"end");Objects.requireNonNull(dictionary,"dictionary");if(begin.isEmpty())throw new IllegalArgumentException("empty word");letters(begin,begin.length());letters(end,begin.length());for(String word:dictionary)letters(word,begin.length());}
 6     public static int ladderLength(String begin,String end,List<String> dictionary) {
 7         validate(begin,end,dictionary);if(begin.equals(end))return 1;
 8         Set<String> unused=new HashSet<>(dictionary);if(!unused.contains(end))return 0;
 9         unused.remove(begin);ArrayDeque<Step> queue=new ArrayDeque<>();queue.addLast(new Step(begin,1));
10         while(!queue.isEmpty()) {
11             Step step=queue.removeFirst();if(step.word.equals(end))return step.length;
12             char[] candidate=step.word.toCharArray();
13             for(int position=0;position<candidate.length;position++) {
14                 char original=candidate[position];
15                 for(char letter='a';letter<='z';letter++) {
16                     if(letter==original)continue;candidate[position]=letter;String neighbor=new String(candidate);
17                     if(unused.remove(neighbor))queue.addLast(new Step(neighbor,step.length+1));
18                 }
19                 candidate[position]=original;
20             }
21         }
22         return 0;
23     }
24     private static boolean adjacent(String a,String b){int differences=0;for(int i=0;i<a.length();i++)if(a.charAt(i)!=b.charAt(i)&&++differences>1)return false;return differences==1;}
25     public static int baseline(String begin,String end,List<String> dictionary) {
26         validate(begin,end,dictionary);if(begin.equals(end))return 1;Set<String> unique=new LinkedHashSet<>(dictionary);if(!unique.contains(end))return 0;unique.add(begin);List<String> words=new ArrayList<>(unique);
27         List<List<Integer>> edges=new ArrayList<>();for(int i=0;i<words.size();i++)edges.add(new ArrayList<>());
28         for(int i=0;i<words.size();i++)for(int j=0;j<i;j++)if(adjacent(words.get(i),words.get(j))){edges.get(i).add(j);edges.get(j).add(i);}
29         int[] distance=new int[words.size()];ArrayDeque<Integer> queue=new ArrayDeque<>();int start=words.indexOf(begin);distance[start]=1;queue.addLast(start);
30         while(!queue.isEmpty()){int vertex=queue.removeFirst();if(words.get(vertex).equals(end))return distance[vertex];for(int next:edges.get(vertex))if(distance[next]==0){distance[next]=distance[vertex]+1;queue.addLast(next);}}return 0;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the starting word and remove it from rediscovery.
Distances count words including the start. Removing a dictionary word on discovery gives it one queue owner.
begin
"aaa"
end
"bbb"
dictionary
["aac","bbb"]
unused
["aac","bbb"]
queue
[{"word":"aaa","length":1}]
distance
[{"word":"aaa","length":1}]
current
null
phase
"seed"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"aaa"
end
"bbb"
dictionary
["aac","bbb"]
unused
["aac","bbb"]
queue
[]
distance
[{"word":"aaa","length":1}]
current
{"word":"aaa","length":1}
phase
"expand"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"aaa"
end
"bbb"
dictionary
["aac","bbb"]
unused
["bbb"]
queue
[{"word":"aac","length":2}]
distance
[{"word":"aaa","length":1},{"word":"aac","length":2}]
current
{"word":"aaa","length":1}
phase
"discover"
position
2
letter
"c"
neighbor
"aac"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"aaa"
end
"bbb"
dictionary
["aac","bbb"]
unused
["bbb"]
queue
[]
distance
[{"word":"aaa","length":1},{"word":"aac","length":2}]
current
{"word":"aac","length":2}
phase
"expand"
The reachable word component is exhausted without the target.
A present target can still be disconnected. Remaining set entries are not reachable by a legal one-letter chain.
begin
"aaa"
end
"bbb"
dictionary
["aac","bbb"]
unused
["bbb"]
queue
[]
distance
[{"word":"aaa","length":1},{"word":"aac","length":2}]
current
{"word":"aac","length":2}
phase
"exhausted"
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
0

One substitution is two words

Input: {"begin":"a","end":"c","dictionary":["b","c"]} · Shortest word count / 0: 2

Step 1 of 7: Seed the starting word and remove it from rediscovery.

Distances count words including the start. Removing a dictionary word on discovery gives it one queue owner.

Word ladder — one-letter edges and word-count distance

Phase: seed.

Start: a. Target: c.

Input dictionary occurrences — original order

Queue — front at left; lengths count words

a: 1

Discovered minimum word counts — teaching history

a: 1

Unused dictionary words — sorted set view

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
begin	`"a"`
end	`"c"`
dictionary	`["b","c"]`
unused	`["b","c"]`
queue	`[{"word":"a","length":1}]`
distance	`[{"word":"a","length":1}]`
current	`null`
phase	`"seed"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private record Step(String word,int length) {}
 4     private static void letters(String word,int length){Objects.requireNonNull(word,"word");if(word.length()!=length)throw new IllegalArgumentException("different word length");for(int i=0;i<word.length();i++)if(word.charAt(i)<'a'||word.charAt(i)>'z')throw new IllegalArgumentException("invalid letter");}
 5     private static void validate(String begin,String end,List<String> dictionary){Objects.requireNonNull(begin,"begin");Objects.requireNonNull(end,"end");Objects.requireNonNull(dictionary,"dictionary");if(begin.isEmpty())throw new IllegalArgumentException("empty word");letters(begin,begin.length());letters(end,begin.length());for(String word:dictionary)letters(word,begin.length());}
 6     public static int ladderLength(String begin,String end,List<String> dictionary) {
 7         validate(begin,end,dictionary);if(begin.equals(end))return 1;
 8         Set<String> unused=new HashSet<>(dictionary);if(!unused.contains(end))return 0;
 9         unused.remove(begin);ArrayDeque<Step> queue=new ArrayDeque<>();queue.addLast(new Step(begin,1));
10         while(!queue.isEmpty()) {
11             Step step=queue.removeFirst();if(step.word.equals(end))return step.length;
12             char[] candidate=step.word.toCharArray();
13             for(int position=0;position<candidate.length;position++) {
14                 char original=candidate[position];
15                 for(char letter='a';letter<='z';letter++) {
16                     if(letter==original)continue;candidate[position]=letter;String neighbor=new String(candidate);
17                     if(unused.remove(neighbor))queue.addLast(new Step(neighbor,step.length+1));
18                 }
19                 candidate[position]=original;
20             }
21         }
22         return 0;
23     }
24     private static boolean adjacent(String a,String b){int differences=0;for(int i=0;i<a.length();i++)if(a.charAt(i)!=b.charAt(i)&&++differences>1)return false;return differences==1;}
25     public static int baseline(String begin,String end,List<String> dictionary) {
26         validate(begin,end,dictionary);if(begin.equals(end))return 1;Set<String> unique=new LinkedHashSet<>(dictionary);if(!unique.contains(end))return 0;unique.add(begin);List<String> words=new ArrayList<>(unique);
27         List<List<Integer>> edges=new ArrayList<>();for(int i=0;i<words.size();i++)edges.add(new ArrayList<>());
28         for(int i=0;i<words.size();i++)for(int j=0;j<i;j++)if(adjacent(words.get(i),words.get(j))){edges.get(i).add(j);edges.get(j).add(i);}
29         int[] distance=new int[words.size()];ArrayDeque<Integer> queue=new ArrayDeque<>();int start=words.indexOf(begin);distance[start]=1;queue.addLast(start);
30         while(!queue.isEmpty()){int vertex=queue.removeFirst();if(words.get(vertex).equals(end))return distance[vertex];for(int next:edges.get(vertex))if(distance[next]==0){distance[next]=distance[vertex]+1;queue.addLast(next);}}return 0;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the starting word and remove it from rediscovery.
Distances count words including the start. Removing a dictionary word on discovery gives it one queue owner.
begin
"a"
end
"c"
dictionary
["b","c"]
unused
["b","c"]
queue
[{"word":"a","length":1}]
distance
[{"word":"a","length":1}]
current
null
phase
"seed"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"a"
end
"c"
dictionary
["b","c"]
unused
["b","c"]
queue
[]
distance
[{"word":"a","length":1}]
current
{"word":"a","length":1}
phase
"expand"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"a"
end
"c"
dictionary
["b","c"]
unused
["c"]
queue
[{"word":"b","length":2}]
distance
[{"word":"a","length":1},{"word":"b","length":2}]
current
{"word":"a","length":1}
phase
"discover"
position
0
letter
"b"
neighbor
"b"
Remove one newly discovered dictionary word and enqueue it once.
The edge changes exactly one position; duplicate input occurrences do not create additional vertices or change the distance.
begin
"a"
end
"c"
dictionary
["b","c"]
unused
[]
queue
[{"word":"b","length":2},{"word":"c","length":2}]
distance
[{"word":"a","length":1},{"word":"b","length":2},{"word":"c","length":2}]
current
{"word":"a","length":1}
phase
"discover"
position
0
letter
"c"
neighbor
"c"
Generate one-letter changes of this immutable word.
Unsuccessful candidate lookups are compressed in this walkthrough. Java copies and hashes each generated String, which contributes a factor of word length.
begin
"a"
end
"c"
dictionary
["b","c"]
unused
[]
queue
[{"word":"c","length":2}]
distance
[{"word":"a","length":1},{"word":"b","length":2},{"word":"c","length":2}]
current
{"word":"b","length":2}
phase
"expand"
Return the first dequeued target’s shortest word count.
FIFO discovery gives minimum edge distance; starting at one converts it to the required number of words. Pending alternatives need not be processed.
begin
"a"
end
"c"
dictionary
["b","c"]
unused
[]
queue
[]
distance
[{"word":"a","length":1},{"word":"b","length":2},{"word":"c","length":2}]
current
{"word":"c","length":2}
phase
"target"
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
2

Test the contract

Input: Equal validated endpoints, empty dictionary
Output: 1
Explicit identity contract.
Input: Missing target
Output: 0
No allowed final changed-to word.
Input: Present but disconnected target
Output: 0
Membership alone is insufficient.
Input: Duplicate words and unmodifiable list
Output: same shortest word count, source preserved
Private discovery set.
Input: 20-position chain
Output: 21 words
Word count and candidate restoration.

Common mistakes and counterexamples

Return number of substitutions

Counterexample: The five-word hit→cog chain has four edits but answer five.

Seed begin length one.

Remove only when popped

Counterexample: Two parents can schedule the same dictionary word.

Remove from the private unused set before enqueueing.

Modify the caller dictionary

Counterexample: An unmodifiable List must still be valid input.

Construct a private set and preserve all original references/order.

Ignore String allocation and hashing

Counterexample: Generating 25L Strings does not cost O(L) total character work per vertex.

Count O(L) work per constructed candidate and distinguish peak from cumulative allocations.

Follow-ups

Return every shortest sequence.

Retain all same-level predecessor edges, not one parent or an immediate global discard that loses alternate shortest parents. Finish the target layer before enumerating paths and account for potentially large output.

Use bidirectional BFS.

Expand the smaller frontier with rigorously tracked sides/layers. Membership removal and meeting conditions need a proof; simply alternating pops from two queues is not enough.

Precompute wildcard buckets.

Map patterns such as h*t to their words, including preprocessing, substring/key construction and bucket-scanning cost. Clear or account for repeated bucket scans; the key-building cost also depends on L.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 189/20,000 characters

Self-review

Can I prove generated candidates change exactly one position?Can I explain why removing on discovery is safe for one shortest-length answer?Can I include character-copy/hash work and preserve the original list?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

BFS: discovery, layers, and multiple sources

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.