題目出處

127. Word Ladder

難度

hard

個人範例程式碼

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0 # not in wordlist

        wordset = set(wordList)
        this_layer = [beginWord]
        visited = set([beginWord])
        distance = 0

        # BFS, thinking of layer
        while this_layer:
            distance += 1 # new bfs layer
            next_layer = []
            for each_word in this_layer:
                if each_word == endWord: # find ans
                    return distance

                for next_word in self.get_next_word(each_word, wordset):
                    if next_word in visited:
                        pass
                    else:
                        next_layer.append(next_word)
                        visited.add(next_word)

            this_layer = next_layer

        return 0 # not found

    def get_next_word(self, each_word, wordset): # find all possible case
        words = [] 
        for i, each_char in enumerate(each_word):
            left, right = each_word[:i], each_word[i+1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if each_word[i] == char:
                    continue
                else:
                    new_word = left + char + right
                    if new_word in wordset:
                        words.append(new_word)

        return words

算法說明

看似 string 其實是一個 Graph 的題目，透過 BFS 來分層遍歷，找到最淺能達到目標的點。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

get_next_word

這裡我們使用的方式比較單純，可以採取的策略有：

• 從 wordList 去反推下一層可能的文字
• 直接拆字去推，再去 wordList 找

個人使用的是第二種方法。

注意：加速技巧

原本題目使用的 wordList 搜尋時間為：O(n)，
若改為 set, hashmap，時間可以壓縮至 O(1)

input handling

處理 input endWord 不在 wordList 的情況，輸出 0 。

Boundary conditions

迴圈結束於

• 找到目標
• 找不到目標，且沒有下一層 layer (全部都 visited)

Reference

• 单词接龙 · Word Ladder
• TimeComplexity