BFSDFSImplicit Graph

## # Solution

### # BFS & DFS (REDO)

a simple Python soln (opens new window)

``````def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
dct = set()
for word in wordList:
distance = {}

self.bfs(endWord, distance, dct)

results = []
self.dfs(beginWord, endWord, distance, dct, [beginWord], results)

return results

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

def get_next_words(self, word, dct):
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 dct:
words.append(next_word)
return words

def dfs(self, curt, target, distance, dct, path, results):
if curt == target:
results.append(list(path))
return

for word in self.get_next_words(curt, dct):
if distance[word] != distance[curt] - 1:
continue
path.append(word)
self.dfs(word, target, distance, dct, path, results)
path.pop()
``````
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