Leetcode - 127. Word Ladder

🔗 Solving the Word Ladder Problem Using BFS in JavaScript

The Word Ladder problem is a classic interview question that combines strings and graphs. It's a brilliant example of applying Breadth-First Search (BFS) to find the shortest path in an implicit graph — where nodes are words and edges are single-letter transformations.

Let’s explore the approach, code, and real-world relevance of this problem.

---

🧩 Problem Statement

You are given:

• A beginWord (e.g., "hit")
• An endWord (e.g., "cog")
• A list of words (wordList) like ["hot", "dot", "dog", "lot", "log", "cog"]

Each move allows you to change a single character, and the resulting word must be present in the word list.

Your goal is to find the shortest number of transformations needed to reach endWord from beginWord.

⚠️ Return 0 if no such transformation sequence exists.

---

🧠 Approach: Breadth-First Search (BFS)

We treat each word as a node, and there's an edge between two nodes if they differ by exactly one letter.

We’ll perform BFS starting from beginWord, exploring all valid 1-letter transformations and tracking levels (i.e., number of transformations).

Key Components:

• Queue for BFS traversal
• Visited Set to avoid revisiting words
• Letter substitution at each character position to generate possible next words
• Early exit when we reach endWord

---

✅ JavaScript Code

var ladderLength = function (beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;

    const letters = "abcdefghijklmnopqrstuvwxyz";
    let queue = [[beginWord, 1]];
    let visited = new Set([beginWord]);

    while (queue.length !== 0) {
        const [word, count] = queue.pop(); // BFS step

        for (let j = 0; j < word.length; j++) {
            for (let i = 0; i < 26; i++) {
                let newWord = word.slice(0, j) + letters[i] + word.slice(j + 1);

                if (!wordSet.has(newWord)) continue;
                if (newWord === endWord) return count + 1;

                if (!visited.has(newWord)) {
                    visited.add(newWord);
                    queue.unshift([newWord, count + 1]); // push to front for BFS
                }
            }
        }
    }

    return 0;
};

---

🧮 Time and Space Complexity

⏱ Time Complexity: O(N * M * 26)

• N = number of words in the list
• M = length of each word
• 26 = number of letters in the alphabet (we try each one at each position)

🗂 Space Complexity: O(N + M)

• For the visited set, queue, and word set.

---

💼 Real-world Applications

Though this is a toy problem, the concept has practical applications in:

• Spell-checkers and autocorrect systems

  • Finding the closest dictionary word to a misspelled one.

• Genetics

  • DNA mutation pathways (each base is A, T, G, or C — similar to letters).

• Network routing / AI

  • Finding shortest paths with transformation constraints.

• Natural language processing (NLP)

  • Word embeddings and similarity graphs.

---

🚀 Summary

The Word Ladder problem shows how powerful and flexible graph algorithms are — even when the graph isn't explicitly given. We dynamically generate neighbors by mutating strings, then use BFS to find the shortest path.

Next time you're facing a "transform from A to B" problem, remember:
👉 It might be a hidden BFS in disguise!

---