Skip to main content

Breadth First Search

Word Ladder

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == 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.

Try here before watching the video.

Video Explanation

Java Code

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);

        int wordCount = 1;
        while(!queue.isEmpty()) {
            int queueSize = queue.size();
            for(int i = 0; i < queueSize; i++) {
                String currWord = queue.poll();
                if(currWord.equals(endWord)) return wordCount;
                char word[] = currWord.toCharArray();
                for(int j = 0; j < word.length; j++) {
                    char ch = word[j];
                    for(char c = 'a'; c <= 'z'; c++) {
                        word[j] = c;
                        String nextWord = new String(word);
                        if(set.contains(nextWord)) {
                            queue.add(nextWord);
                            set.remove(nextWord);
                        }
                    }
                    word[j] = ch;
                }
            }
            wordCount += 1;
        }
        return 0;
    }
}

C++ Code

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        
        queue<string> q;
        q.push(beginWord);
        
        int wordCount = 1;
        while (!q.empty()) {
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i) {
                string currWord = q.front();
                q.pop();
                
                if (currWord == endWord) {
                    return wordCount;
                }
                
                for (int j = 0; j < currWord.size(); ++j) {
                    char originalChar = currWord[j];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        currWord[j] = c;
                        if (wordSet.find(currWord) != wordSet.end()) {
                            q.push(currWord);
                            wordSet.erase(currWord);
                        }
                    }
                    currWord[j] = originalChar;
                }
            }
            wordCount += 1;
        }
        
        return 0;
    }
};

Python Code

from typing import List
from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        
        queue = deque([beginWord])
        word_count = 1
        while queue:
            queue_size = len(queue)
            for i in range(queue_size):
                curr_word = queue.popleft()
                if curr_word == endWord:
                    return word_count
                
                word_list = list(curr_word)
                for j in range(len(word_list)):
                    original_char = word_list[j]
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        word_list[j] = c
                        next_word = ''.join(word_list)
                        if next_word in word_set:
                            queue.append(next_word)
                            word_set.remove(next_word)
                    word_list[j] = original_char
            
            word_count += 1
        
        return 0

Javascript Code

Go Code

func ladderLength(beginWord string, endWord string, wordList []string) int {
	set := make(map[string]bool)
	for _, word := range wordList {
		set[word] = true
	}

	queue := []string{beginWord}
	wordCount := 1

	for len(queue) > 0 {
		queueSize := len(queue)
		for i := 0; i < queueSize; i++ {
			currWord := queue[0]
			queue = queue[1:]

			if currWord == endWord {
				return wordCount
			}

			word := []rune(currWord)
			for j := 0; j < len(word); j++ {
				ch := word[j]
				for c := 'a'; c <= 'z'; c++ {
					word[j] = c
					nextWord := string(word)
					if set[nextWord] {
						queue = append(queue, nextWord)
						delete(set, nextWord)
					}
				}
				word[j] = ch
			}
		}
		wordCount++
	}

	return 0
}

Complexity Analysis

  • Time Complexity: O(M2×N), where M is the length of words and N is the total number of words in the input word list.
  • Space Complexity: O(M2×N), to store all M transformations for each of the N words.