The O(n) Club: Word Ladder II – BFS, DFS, and the Great Shortest-Path Scavenger Hunt

The O(n) Club: Word Ladder II – BFS, DFS, and the Great Shortest-Path Scavenger Hunt

⚡ TL;DR

You need to find all the shortest word ladders between two words, not just one ladder for bragging rights. Brute-force is for the bold (or bored) and will absolutely throttle your CPU into next week. Let BFS map out the shortest ladders, then use DFS/backtracking to splice those paths together. Here’s how not to pull this off:

// Brute force: Spoiler, your laptop fan won't forgive you
dfs(String word, String end, Set
<string> dict, List<string> path) {
    if (word.equals(end)) results.add(new ArrayList<>(path));
    for (String next : nextWords(word, dict)) {
        dict.remove(next);
        path.add(next);
        dfs(next, end, dict, path);
        path.remove(path.size()-1);
        dict.add(next);
    }
}</string></string>

🧠 How Devs Usually Mess This Up

Imagine spending 20 minutes fine-tuning a BFS that finds a single “optimal” ladder, then discovering the question wanted all shortest ladders. Oops. Or maybe you code up a standard BFS, hit the endWord, and celebrate way too early—ignoring the 17 other valid shortest sequences. Some copy-paste the solution from Word Ladder I, blissfully unaware that now you need to output all paths instead of just counting steps. If you don’t store “who led to me” at every BFS level, you’ll only remember one journey through this word soup—and your interviewer will definitely notice.

🔍 What’s Actually Going On

Picture every word as a node in a social graph—”hot” knows “dot” and “lot,” but treats “dog” like an acquaintance. BFS dutifully explores word-friends, level by level, logging who each word’s “parents” are for any shortest route that arrives. Only after BFS finishes should you unleash DFS/backtracking to artfully reconstruct all the shortest ladders—kind of like genealogy, if all your relatives were one typo away from you. BFS is your Uber; DFS is your friend with the photos.

🛠️ PseudoCode

• Build your graph:
  • Each word is a node. Edges connect words differing by one letter.
• Do a BFS:
  • Start at beginWord. Queue tracks all possible next words.
  • For each neighbor you discover, store the “parent” and add to the queue if new, or to its parent list if already discovered this level.
  • Stop searching deeper when you hit the endWord for the first time—congrats, all shortest paths are at that BFS level.
• DFS/backtrack all the paths:
  • Use your parent map to backtrack from endWord to beginWord, recording every possible minimal ladder.