Last updated on March 1st, 2025 at 08:09 pm

Here, we see a Word Ladder LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Breadth-First Search

Companies

Amazon, Facebook, LinkedIn, Snapchat, Yelp

Level of Question

Hard

Word Ladder LeetCode Solution

1. Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s₁ -> s₂ -> ... -> s_k such that:

Every adjacent pair of words differs by a single letter.
Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
s_k == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: 5
Explanation: One shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> cog”, which is 5 words long.

Example 2:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Graph Breadth-First Search (BFS)”. This is because the problem involves finding the shortest transformation sequence from the beginWord to the endWord by changing one letter at a time, which is analogous to finding the shortest path in an unweighted graph. Each word is treated as a node, and an edge exists between two nodes if they differ by exactly one character.

3. Code Implementation in Different Languages

3.1 Word Ladder C++

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> todo;
        todo.push(beginWord);
        int ladder = 1;
        while (!todo.empty()) {
            int n = todo.size();
            for (int i = 0; i < n; i++) {
                string word = todo.front();
                todo.pop();
                if (word == endWord) {
                    return ladder;
                }
                dict.erase(word);
                for (int j = 0; j < word.size(); j++) {
                    char c = word[j];
                    for (int k = 0; k < 26; k++) {
                        word[j] = 'a' + k;
                        if (dict.find(word) != dict.end()) {
                            todo.push(word);
                        }
                     }
                    word[j] = c;
                }
            }
            ladder++;
        }
        return 0;
    }
};

3.2 Word Ladder Java

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        Set<String> dict = new HashSet<>(wordList);
        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        beginSet.add(beginWord);
        endSet.add(endWord);
        int step = 1;
        Set<String> visited = new HashSet<>();
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            if (beginSet.size() > endSet.size()) {
                Set<String> set = beginSet;
                beginSet = endSet;
                endSet = set;
            }
            Set<String> temp = new HashSet<>();
            for (String word : beginSet) {
                char[] chs = word.toCharArray();
                for (int i = 0; i < chs.length; i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        char old = chs[i];
                        chs[i] = c;
                        String target = String.valueOf(chs);
                        if (endSet.contains(target)) {
                            return step + 1;
                        }
                        if (!visited.contains(target) && dict.contains(target)) {
                            temp.add(target);
                            visited.add(target);
                        }
                        chs[i] = old;
                    }
                }
            }
            beginSet = temp;
            step++;
        }
        return 0;
    }
}

3.3 Word Ladder JavaScript

var ladderLength = function(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList)
    let queue = [beginWord];
    let steps = 1;
    while(queue.length) {
        const next = [];
        for(let word of queue) {
            if(word === endWord) return steps;
            for(let i = 0; i < word.length; i++) {
                for(let j = 0; j < 26; j++) {
                    const newWord = word.slice(0, i) + String.fromCharCode(j + 97) + word.slice(i+1);
                    if(wordSet.has(newWord)) {
                        next.push(newWord);
                        wordSet.delete(newWord);
                    }
                }
            }
        }
        queue = next
        steps++;
    }
    return 0;    
};

3.4 Word Ladder Python

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordDict):
        if endWord not in wordDict:
            return 0
        length = 2
        front, back = set([beginWord]), set([endWord])
        wordDict = set(wordDict)
        wordDict.discard(beginWord)
        while front:
            front = wordDict & (set(word[:index] + ch + word[index+1:] for word in front 
                                for index in range(len(beginWord)) for ch in string.ascii_lowercase))
            if front & back:
                return length
            length += 1
            if len(front) > len(back):
                front, back = back, front
            wordDict -= front
        return 0

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(N * L)	O(N)
Java	O(N * L)	O(N)
JavaScript	O(N * L)	O(N)
Python	O(N * L)	O(N)

here,
N is the number of words in the wordList.
L is the length of each word.

The BFS ensures that the shortest path is found, as it explores all nodes at the current depth before moving to the next depth.
The space complexity is dominated by the storage of the word list and the BFS queue or sets.