【Leetcode】python – [126] Word Ladder II 個人解法筆記

➣ Reading Time: 10 minutes

題目出處

126. Word Ladder II

難度

hard

個人範例程式碼

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        if endWord not in wordList:
            return []

        wordList.append(beginWord)
        distance = {}

        self.bfs(endWord, distance, wordList) # from end to start
        self.ans = []
        self.dfs(beginWord, endWord, distance, wordList, [beginWord]) # from start to end

        return self.ans

    def bfs(self, start, distance, worddict):
        distance[start] = 0
        queue = deque([start])
        while queue:
            word = queue.popleft()
            print(self.get_next_words(word, worddict))
            for next_word in self.get_next_words(word, worddict):
                if next_word not in distance:
                    distance[next_word] = distance[word] + 1
                    queue.append(next_word)

    def get_next_words(self, word, worddict):
        words = []
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word != word and next_word in worddict:
                    words.append(next_word)
        # print(words)
        return words

    def dfs(self, cur, target, distance, worddict, path):
        # print(distance)
        if cur == target:
            self.ans.append(path[:])
            return

        for word in self.get_next_words(cur, worddict): # different way will see other things
            if word not in distance: # single node
                continue
            if distance[word] != distance[cur] - 1:
                continue
            path.append(word)
            self.dfs(word, target, distance, worddict, path)
            path.pop() # backtracking

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

算法說明

超難的一題,考了非常多概念,對細節處理的要求也非常多
我們先從建立圖片下手。

從 BFS 先找到最短路徑

題目的做成的文字圖有可能會有循環,我們需要先找最短路徑

透過最短路徑,反向 DFS 尋找所有結果

知道最短路徑後,我們才能用 DFS 將整個圖走過,
看在最短路徑的範圍當中,能夠找到有幾種結果。

  • 先從 endWord 找回 start,再從 start 順便存路徑會最順。

注意處

從兩個起點搜尋的注意事項

這邊要處理在從兩端搜尋時,還是都要把每個點都看過一次,
例如上圖中下方的 graph 結構,我們會發現會有一些只靠單向搜尋「會距離很遠」的位置

獨立的點

有一種特殊的 case 是從起點開始,就根本就沒有任何的連線,
雖然這題的測資沒有考到,但這邊一樣有處理。

  • 狀況大概如下圖:

只能說,這個就是細節處理的部分,萬一真的有這樣的情況,我們還是要回傳 []

input handling

如果 endWord 不在 worddict 中,return []

Boundary conditions

BFS 找最短路徑

搜尋至 queue 沒有東西的時候
「while queue」幫忙控制結束

DFS 找所有結果

反向搜尋至 distance 為 0 時結束,
我們在上一步驟中的 BFS,有順便記錄了 distance 最大的長度,
這邊就是反向操作到 0。

Reference

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 728

★留個言吧!內容有誤或想要補充也歡迎與我討論!