127. Word Ladder

• categories: Code, Interview Question, leetcode, Hard
• source: https://leetcode.com/problems/word-ladder
• topics: Graph, BFS

Description

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.

Idea

• First idea : BFS in graph, same as 433. Minimum Genetic Mutation
• BFS in graph using char counters and words set to reduce the number of lookups

Code

BFS in graph

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if not wordList or endWord not in wordList:
            return 0
        if beginWord == endWord and endWord in wordList:
            return 0
 
        def is_neighbour(s1, s2):
            counter = 0
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    if counter == 1:
                        return False
                    counter += 1
                    
            return counter == 1
 
        visited = set(s for s in wordList if is_neighbour(s, beginWord))
        queue = deque(visited)
        step = 1
        
        while queue:
            step += 1
            for _ in range(len(queue)):
                curr = queue.popleft()
                
                if curr == endWord:
                    return step
 
                for s in wordList:
                    if s not in visited and is_neighbour(curr, s):
                        visited.add(s)
                        queue.append(s)
 
        return 0

BFS with char counters

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list) -> int:
        wordSet = set(wordList)  # Convert list to set for fast lookup
        if endWord not in wordSet:
            return 0
        if beginWord in wordSet:
            wordSet.remove(beginWord)
        counters = [Counter() for _ in range(len(wordList[0]))]
 
        for w in wordSet:
            for i in range(len(w)):
                counters[i][w[i]] += 1
        
        queue = deque([beginWord])  # BFS queue storing (word, steps)
        steps = 0
        while queue:
            steps += 1
            for _ in range(len(queue)):
                word = queue.popleft()
 
                if word == endWord:
                    return steps
 
                for i in range(len(word)):
                    original = word[i]
                    for ch in counters[i].keys():  # Check all possible single character changes
                        candidate = word[:i] + ch + word[i + 1:]
                        if candidate in wordSet:
                            wordSet.remove(candidate)  # Avoid revisiting
                            queue.append(candidate)
 
            # Update char counters
            for q in queue:
                for i in range(len(q)):
                    counters[i][q[i]] -= 1
                    if not counters[i][q[i]]:
                        del counters[i][q[i]]
        
        return 0  # If no valid transformation is found