HardLeetCode #127Graphs

Word Ladder

A transformation sequence from beginWord to endWord using dictionary wordList is a sequence where every adjacent pair of words differs by a single letter and every word is in wordList. Return the number of words in the shortest transformation sequence, or 0 if no such sequence exists.

Constraints

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

Examples

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

Output: 5

Solution

Approach

BFS from beginWord. For each word, generate all possible one-letter variations and check if they exist in wordList. Track visited words.

from collections import deque
def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, length = queue.popleft()
        if word == endWord:
            return length
        for i in range(len(word)):
            for c in "abcdefghijklmnopqrstuvwxyz":
                next_word = word[:i] + c + word[i+1:]
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, length + 1))
    return 0

Complexity

Time:O(M² * N)

Space:O(M * N)

Hints

1.BFS finds shortest path in unweighted graph
2.Nodes are words, edges connect words differing by one letter
3.Generate neighbors by changing each position

Asked at

Google