126. Word Ladder II

126. Word Ladder II

做這一題之前要先了解 127. Word Ladder 。這一題稍微不一樣的是,我們要舉出所有的路徑。

這一個題目需要注意的是,廣度優先搜索一定要一層一層的搜索,不能一步一步的搜索,因為當我們找到答案的同時,掃瞄完該層時,就會有所有的組合了,可以快速的找到答案,但如果是一步一步走,那就會變成要窮舉完,後面的探索都是無效的。

比較特別的是這裡和回溯法有一點點類似的地方,那就是既然是一層一層走,一個單字在該層都算是可以使用的,因此在記錄已經造訪過的點的方法,要用 union set 的方式紀錄(這是一個比較少用的 API)。但是不記得此 API 也沒關係,可以透過一個迴圈再把所有的 word 加進去。

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

        def maskWord(word, i=0):
            return word[:i] + '*' + word[i+1:]

        L = len(beginWord)
        table = defaultdict(list)

        for i in range(L):
            for word in wordList:
                table[maskWord(word, i)].append(word)

        q = deque([(beginWord, [beginWord])])
        seen = set([beginWord])
        ans = []

        while q:
            size = len(q)
            local = set()
            for i in range(size):
                word, path = q.popleft()
                for j in range(L):
                    for next_word in table[maskWord(word, j)]:
                        if next_word == endWord:
                            ans.append(list(path + [next_word]))
                        if next_word not in seen:
                            q.append((next_word, path + [next_word]))
                            local.add(next_word)
            if ans:
                break
            seen = seen.union(local)
        return ans