126. Word Ladder II

https://leetcode.com/problems/word-ladder-ii/

Python

Backtracking (Timelimit Exceed)

• 題目只想要求shortest transformation sequences，但這個backtrack會找出所有可能的路徑
• 自己寫的留個紀錄

from collections import defaultdict
from string import ascii_lowercase


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

        word_set = set(wordList)

        mapper = defaultdict(set)
        for word in word_set | set([beginWord]):
            for i in range(len(word)):
                for char in ascii_lowercase:
                    new_word = word[:i] + char + word[i+1:]
                    if char != word[i] and new_word in word_set:
                        mapper[word].add(new_word)

        def backtrack(path, result):
            last = path[-1]

            if last == endWord:
                result.append(path[:])
                return

            for word in mapper[last]:
                if word in path:
                    continue
                path.append(word)
                backtrack(path, result)
                path.pop()

        candidates = []
        backtrack([beginWord], candidates)

        if not candidates:
            return []

        result = dict()
        for cand in candidates:
            if len(cand) not in result:
                result[len(cand)] = []
            result[len(cand)].append(cand)

        return result[min(result.keys())]