127. Word Ladder

Problem Statement

link: https://leetcode.com/problems/word-ladder/ https://leetcode.cn/problems/word-ladder/

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:

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

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

Solution Approach

The problem can be visualized as searching for the shortest path in a graph where each word is a node connected to other words that can be formed by changing a single letter.

Algorithm

1. Preprocess the Words: Construct a dictionary where the key is a generic word with a wildcard character (like ‘_’) and the value is a list of words from the wordList which match the key pattern. This will help in identifying adjacent nodes (words) in the graph.
2. Bidirectional BFS: Initiate a BFS from both the beginWord and endWord. If the BFS from either direction encounters a word seen by the opposite BFS, a valid sequence is found.
3. Optimization: During each BFS iteration, always expand the frontier from the side with fewer nodes. This makes the algorithm more efficient by exploring less in the BFS.

Implement

    class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = set(wordList)
        if endWord not in wordList:
            return 0
        wordList.add(beginWord)
        l = len(beginWord)
        dic = defaultdict(list)
        for word in wordList:
            for i in range(l):
                tmp = word[:i] + '_' + word[i + 1:]
                dic[tmp].append(word)
        q1 = deque([beginWord])
        dis1 = {w: 0 for w in wordList}
        dis1[beginWord] = 1
        q2 = deque([endWord])
        dis2 = {w:0 for w in wordList}
        dis2[endWord] = 1
        flag = True
        while q1 and q2:
            if flag:
                front, dis_front = q1, dis1
                back, dis_back = q2, dis2
            else:
                front, dis_front = q2, dis2
                back, dis_back = q1, dis1
            cur = front.popleft()
            dist = dis_front[cur]
            next_word = []
            for i in range(l):
                tmp = cur[:i] + '_' + cur[i + 1:]

                for w in dic[tmp]:
                    next_word.append(w)
            for w in next_word:
                if dis_back[w] > 0:
                    return dist + dis_back[w]
                if dis_front[w] == 0:
                    dis_front[w] = dist + 1
                    front.append(w)
            if len(back) < len(front):
                flag = not flag
        return 0

    
    

Twitter  facebook  Email