Graph - DSA: Word Ladder - I | Shortest Paths

This chapter covers the classic Word Ladder - I problem. We explore how to transform a given start word into a target word by modifying a single character at a time, ensuring that every intermediate word exists in a provided dictionary. We analyze the brute force approach, transition to a level-order traversal using Breadth-First Search (BFS) to guarantee the shortest transformation sequence, and optimize lookups using an Unordered Set.

1. Problem Statement & Formal Definition

We are given two distinct words—a start word and a target word—along with a word list containing unique words of equal length. Our goal is to find the length of the shortest transformation sequence from the start word to the target word.

Core Rules & Constraints:

• Lowercase Only: All words consist exclusively of lowercase English characters.
• Single Character Modification: Exactly one letter can be changed in each transformation step.
• Dictionary Validation: Each transformed intermediate word (including the target word) must exist within the provided word list.
• Start Word Status: The start word may or may not be present in the word list.
• Failure Condition: If it is impossible to transform the start word into the target word, return 0.

2. Real-Life Analogy: Navigating City Routes

Real-Life Analogy: Stepping Between Cities

Mental Hook: Imagine traveling from a starting city (Odisha) to a destination city (Kerala) across a map where roads only connect cities differing by a single spelling landmark. Each intermediate town must exist on our approved map (the word list). Because we want to save fuel and time, we want the shortest path (fewest steps). A level-by-level exploration guarantees that the moment we step foot into Kerala for the very first time, we have taken the absolute fewest highways possible.

3. Brute Force Exploration & Analysis

Let's examine how the transformation works with a concrete example.

• Start Word: hit
• Target Word: cog
• Word List: ["hot", "dot", "dog", "lot", "log", "cog"]

If we start with hit, we can change any one of its 3 characters:

1. Change character at index 0 (H -> A through Z): AIT, BIT, CIT, ..., ZIT.
2. Change character at index 1 (I -> A through Z): HAT, HBT, ..., HOT, ..., HZT.
3. Change character at index 2 (T -> A through Z): HIA, HIB, ..., HIZ.

Why Brute Force Fails Efficiently:

Scanning an array of size $N$ linearly for every single alphabet change ($26 \times \text{word length}$) is extremely slow. We need an O(1) or O(log N) data structure to check if generated words exist in our dictionary.

4. Core Mental Model: Why BFS for Shortest Paths?

When a problem asks for the shortest path or minimum sequence length in an unweighted graph where every transition costs 1 step, Breadth-First Search (BFS) is the optimal choice.

• Why BFS over DFS? DFS explores deep down one branch, which might lead to a long, convoluted sequence before finding the target. BFS explores level by level, guaranteeing that the first time we pop the target word from our queue, we have found the absolute shortest sequence.

5. Step-by-Step Algorithm & Dry Run

The Optimization: Hash Set for $O(1)$ Lookups & Visited Management

Instead of searching through a vector repeatedly, we load all words into an unordered set. Furthermore, once a word is visited (dequeued and processed), we erase it from the set. This prevents cycles and redundant processing without needing a separate visited array.

Complete Dry Run Walkthrough:

1. Initialize Queue & Set:

   • Queue: [("hit", 1)]
   • Set: {"hot", "dot", "dog", "lot", "log", "cog"}
   • Erase "hit" from set if present.

2. Pop ("hit", 1):

   • Try changing H, I, T.
   • Changing I to O yields "hot".
   • Check Set: "hot" exists!
   • Erase "hot" from Set. Push ("hot", 2) to Queue.

3. Pop ("hot", 2):

   • Try changing H, O, T.
   • Yields "dot" and "lot".
   • Both exist in Set. Erase them. Push ("dot", 3) and ("lot", 3) to Queue.

4. Pop ("dot", 3):

   • Yields "dog".
   • Exists in Set. Erase it. Push ("dog", 4) to Queue.

5. Pop ("lot", 3):

   • Yields "log".
   • Exists in Set. Erase it. Push ("log", 4) to Queue.

6. Pop ("dog", 4):

   • Yields "cog".
   • Exists in Set. Erase it. Push ("cog", 5) to Queue.

7. Pop ("cog", 5):

   • "cog" matches the target word! Return step count 5.

6. Complete C++ Implementation

#include <vector>
#include <string>
#include <queue>
#include <unordered_set>

class Solution {
public:
    int ladderLength(string startWord, string targetWord, vector<string>& wordList) {
        // Queue stores a pair of {current_word, sequence_length}
        queue<pair<string, int>> q;
        q.push({startWord, 1});

        // Store all words in an unordered set for O(1) average lookup time
        unordered_set<string> st(wordList.begin(), wordList.end());
        
        // Remove startWord from set to mark it as visited
        st.erase(startWord);

        while (!q.empty()) {
            string word = q.front().first;
            int steps = q.front().second;
            q.pop();

            // If we reached the target word, return the step count
            if (word == targetWord) {
                return steps;
            }

            // Traverse each character of the current word
            for (int i = 0; i < word.size(); i++) {
                char originalChar = word[i];

                // Replace character with 'a' through 'z'
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    word[i] = ch;

                    // If the newly formed word exists in the set
                    if (st.find(word) != st.end()) {
                        st.erase(word);             // Mark as visited by removing from set
                        q.push({word, steps + 1});  // Push to queue with incremented step
                    }
                }
                // Restore original character before moving to the next position
                word[i] = originalChar;
            }
        }

        // If queue becomes empty without reaching target word
        return 0;
    }
};

7. Complexity Analysis

Summary and Key Takeaways

• Problem Nature: Finding the shortest transformation sequence points directly to Breadth-First Search (BFS) rather than Depth-First Search.
• Level-Order Guarantee: BFS guarantees that the first time the target word is popped from the queue, its sequence length is the absolute minimum possible.
• Optimization via Hash Set: Using an unordered_set allows $O(1)$ average time complexity lookups instead of scanning arrays linearly.
• Implicit Visited State: Deleting words from the hash set upon discovery effectively replaces a separate visited boolean array, preventing cycles.
• Character Substitution Trick: Iterate through every character index of the word, substitute characters from 'a' to 'z', and check validity instantly.
• Restoration Step: Always restore the modified character back to its originalChar after checking all 26 possibilities to keep the string intact for subsequent iterations.
• Failure Handling: If the queue empties completely without encountering the target word, the transformation is impossible, and we return 0.