Leetcode 126. Word Ladder II_a transformation sequence from word beginword to w

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, …, sk].

Constraints:

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 1000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.

Algorithm

Use bfs to find the shortest path and use dfs to print the path.

Code

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        sLen = len(wordList)
        find_end = 0
        find_begin = 0
        bLen = len(beginWord)
        wLen = [bLen] * (sLen+1)
        for i in range(sLen):
            if wordList[i] == endWord:
                find_end = i + 1
            if wordList[i] == beginWord:
                find_begin = i + 1
            wLen[i+1] = len(wordList[i])
        if not find_end:
            return []
        
        if not find_begin:
            wordList = [beginWord] + wordList[:]
        else:
            wordList = [""] + wordList[:]
        
        maps = [[0 for i in range(sLen+1)] for j in range(sLen+1)]
        for i in range(sLen+1):
            if find_begin and i == 0:
                continue
            for j in range(i+1, sLen+1):
                if wLen[i] != bLen:
                    continue
                cnt = 0
                for k in range(bLen):
                    cnt += (wordList[i][k] != wordList[j][k])
                if cnt == 1:
                    maps[i][j] = 1
                    maps[j][i] = 1
        
        # bfs for shortest path
        find = [0] * (sLen + 1)
        find[find_begin] = 1
        head, tail = 0, 1
        Q = [find_begin] * (sLen + 1)
        Step = [1] * (sLen + 1)
        
        smap = [[0 for i in range(sLen+1)] for j in range(sLen+1)]
        while head < tail:
            now = Q[head]
            for i in range(sLen+1):
                if maps[now][i]:
                    if find[i] and Step[now]+1 == Step[i]:
                        smap[now][i] = 1
                    elif not find[i]:
                        smap[now][i] = 1
                        Q[tail] = i
                        find[i] = 1
                        Step[i] = Step[now] + 1
                        tail += 1
            head += 1
        
        ans = []
        buf = []
        def output(i):
            nonlocal buf
            if i == find_begin:
                buf.insert(0, wordList[i])
                ans.append(buf)
                buf = buf[1:]
                return
            for j in range(sLen+1):
                if smap[j][i]:
                    buf.insert(0, wordList[i])
                    output(j)
                    buf = buf[1:]
        output(find_end)
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74