LeetCode Solution 127 - Word Ladder

Problem Statement

Given two words, beginWord and endWord, and a dictionary of words wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:

• Only one letter can be changed at a time.
• Each transformed word must exist in the word list.
• Return 0 if there is no such transformation sequence.

Example:

Input:

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation:

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

Optimal Approach

The best approach to solving this problem is to use Breadth-First Search (BFS), as it ensures the shortest transformation sequence is found first. The BFS explores level by level, making it ideal for shortest path problems.

Algorithm:

1. Convert wordList into a set for quick lookup.
2. Use a queue to store words along with their depth (transformation count).
3. Perform BFS:
   • Dequeue a word and try transforming it by changing each letter.
   • If the transformed word exists in the wordList, enqueue it and remove it from the set.
   • If endWord is reached, return the transformation count.
4. If endWord is never reached, return 0.

LeetCode-Compatible C++ Solution

#include <iostream>
#include <unordered_set>
#include <queue>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) return 0;

        queue<pair<string, int>> q;
        q.push({beginWord, 1});

        while (!q.empty()) {
            auto [word, level] = q.front(); q.pop();
            if (word == endWord) return level;
            
            for (int i = 0; i < word.size(); i++) {
                string temp = word;
                for (char c = 'a'; c <= 'z'; c++) {
                    temp[i] = c;
                    if (wordSet.find(temp) != wordSet.end()) {
                        q.push({temp, level + 1});
                        wordSet.erase(temp);
                    }
                }
            }
        }
        return 0;
    }
};

Step-by-Step Explanation

1. Convert wordList into a set for quick lookups.
2. Initialize a queue with the beginWord and start the level count at 1.
3. Start BFS traversal:
   • Extract the front element.
   • Try replacing each character with a-z.
   • If the new word is in wordList, push it into the queue and remove it from the set.
   • Stop when endWord is found.

Dry Run / Execution Steps

Input:

beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Execution:

Step	Queue State	Level
1	{"hit",1}	1
2	{"hot",2}	2
3	{"dot",3}, {"lot",3}	3
4	{"dog",4}, {"log",4}	4
5	{"cog",5}	5 (Found endWord)

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
DFS	Exponential	High	Can get stuck in longer paths
Bidirectional BFS	O(N)	O(N)	Faster but complex to implement

Best Solution & Why It’s Best

The BFS approach is optimal because it finds the shortest transformation path without exploring unnecessary branches. Time Complexity is O(N * M * 26) where N is the number of words, and M is the length of each word.

Complexity Analysis

• Time Complexity: O(N * M * 26), where N is the number of words and M is the length of each word.
• Space Complexity: O(N), for storing words in the queue and set.

Conclusion

• The BFS approach is the best for solving Word Ladder.
• This ensures the shortest transformation sequence is found first.
• Practice similar problems:
  • Word Ladder II
  • Shortest Path in a Grid

This structured approach will help solve the Word Ladder problem efficiently and effectively.