BFS Word Ladder

126. Word Ladder II

A naive solution is here

class Solution:
    def findLadders(self, begin: str, end: str, wordList: List[str]) -> List[List[str]]:
        word_set = set(wordList)
        res = []
        def bfs(begin, hist):
            Q = collections.deque([(begin, hist+[begin], 0)])
            seen = collections.defaultdict(int)
            seen[begin] = 0
            target_d = float('inf')
            while Q:
                word, hist, d = Q.popleft()
                if d>target_d:break
                for i, c in enumerate(word):
                    for new_c in [chr(ord('a')+j) for j in range(26)]:
                        if new_c != c:
                            new_word = word[:i]+new_c+word[i+1:]
                            if new_word in word_set and new_word not in seen or seen[new_word]==d+1:
                                if new_word == end:
                                    target_d = d
                                    res.append(hist+[new_word])
                                elif d+1<=target_d:
                                    seen[new_word]=d+1
                                    Q.append((new_word, hist+[new_word], d+1))
        bfs(begin, [])
        return res

It is slow and the running time is about

Runtime: 4408 ms, faster than 5.08% of Python3 online submissions for Word Ladder II.
Memory Usage: 55.8 MB, less than 8.33% of Python3 online submissions for Word Ladder II.

This one is slightly faster

class Solution:
    def findLadders(self, begin: str, end: str, wordList: List[str]) -> List[List[str]]:
       
        res = []
        def bfs(begin):
            word_set = set(wordList)
            if end not in word_set:return
            level = [(begin, begin)]
            found = False
            while level and not found:
                new_level = []
                for word, hist in level:      
                    for i in range(len(word)):
                        for new_c in "abcdefghijklmnopqrstuvwxyz":
                            new_word = word[:i]+new_c+word[i+1:]
                            if new_word in word_set:
                                if new_word == end:
                                    found = True
                                    res.append(hist+","+new_word)
                                else:
                                    new_level.append((new_word, hist+','+new_word))
                word_set-={w for w, _ in new_level}
                level = new_level
        bfs(begin)
        return [r.split(',') for r in res] if res else []