BFS for Layered State Spaces in Java

Preamble

Breadth-first search explores a graph layer by layer—distance 0, then 1, then 2—so the first time you dequeue a node is via a shortest path in unweighted graphs. Word ladder is the classic state-space form: each word is a node; edges connect words one edit apart. Java gives us ArrayDeque for the queue and HashSet/HashMap for visited states and parent pointers.

Adjacency trick

Naive “compare every pair of words” is O(n²) on large dictionaries. Bucket by pattern—replace each character with a wildcard (hit → *it, h*t, hi*)—so words sharing a bucket are neighbors. Building those buckets is O(n × wordLength) with careful hashing.

Path reconstruction

Store parent maps when the problem asks for the ladder sequence, not only the length. BFS stops at the target; walk parents backward to emit the path.

Conclusion

Language changes; invariant narration stays: BFS = shortest hops when edges cost one. Breadth-First Search and Shortest Path Layers in Python shows the same idea in Python; Algorithms Retrospective: DFS, BFS, Dijkstra, and Backtracking connects BFS to interview study loops.