HardBlind75StringBFSHash Table

Word Ladder

Given two words (beginWord and endWord) and a wordList, find the length of the shortest transformation sequence from beginWord to endWord, changing only one letter at a time.

Examples

Input
beginWord = 'hit', endWord = 'cog', wordList = ["hot","dot","dog","lot","log","cog"]
Output
5

hit -> hot -> dot -> dog -> cog, length 5.

Input
beginWord = 'hit', endWord = 'cog', wordList = ["hot","dot","dog","lot","log"]
Output
0

The endWord 'cog' is not in wordList.

Constraints

  • •1 <= beginWord.length <= 10
  • •endWord.length == beginWord.length
  • •1 <= wordList.length <= 5000
  • •wordList[i].length == beginWord.length
  • •beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • •beginWord != endWord

Approaches

Use BFS to find shortest path, generating neighbors by changing one letter.

CodeT: O(M^2 * N) | S: O(M * N)
from collections import deque

def ladder_length(beginWord, endWord, wordList):
    wordList = set(wordList)
    if endWord not in wordList:
        return 0
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, length = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                if new_word == endWord:
                    return length + 1
                if new_word in wordList and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, length + 1))
    return 0

Use pattern-based neighbor lookup for faster neighbor finding.

CodeT: O(M^2 * N) | S: O(M * N)
from collections import defaultdict, deque

def ladder_length(beginWord, endWord, wordList):
    wordList = set(wordList)
    if endWord not in wordList:
        return 0
    pattern_dict = defaultdict(list)
    for word in wordList:
        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]
            pattern_dict[pattern].append(word)
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, length = queue.popleft()
        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]
            for neighbor in pattern_dict[pattern]:
                if neighbor == endWord:
                    return length + 1
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, length + 1))
    return 0

BFS from both beginWord and endWord, meeting in the middle.

Diagram

begin='hit', end='cog' Front: {hit}, Back: {cog} Level 1: hit -> hot Level 1: cog -> dog, log Level 2: hot -> dot, lot Level 2: dog -> dot, lot Meet at dot/lot -> length = 5
CodeT: O(M^2 * N) | S: O(M * N)
from collections import defaultdict, deque

def ladder_length(beginWord, endWord, wordList):
    wordList = set(wordList)
    if endWord not in wordList:
        return 0
    if beginWord in wordList:
        wordList.remove(beginWord)
    front = {beginWord}
    back = {endWord}
    length = 1
    while front and back:
        if len(front) > len(back):
            front, back = back, front
        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in back:
                        return length + 1
                    if new_word in wordList:
                        next_front.add(new_word)
                        wordList.remove(new_word)
        front = next_front
        length += 1
    return 0

Complexity Comparison

BFS - Level by Level
T: O(M^2 * N)S: O(M * N)

Use BFS to find shortest path, generating neighbors by changing one letter.

BFS with Pattern Matching
T: O(M^2 * N)S: O(M * N)

Use pattern-based neighbor lookup for faster neighbor finding.

Bidirectional BFS
T: O(M^2 * N)S: O(M * N)

BFS from both beginWord and endWord, meeting in the middle.

Common Mistakes

Not checking if endWord is in wordList first

Generating all possible words instead of only valid ones

Using bidirectional BFS without checking the meeting condition correctly

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems