-
Notifications
You must be signed in to change notification settings - Fork 0
/
127 word ladder problem.py
47 lines (33 loc) · 1.48 KB
/
127 word ladder problem.py
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
class Solution:
def getWildcard(self, word, i):
return word[:i] + '*' + word[i + 1:]
#this build adjancy list of word differing by one letter
def buildWildcardToWords(self, wordList):
wildcardToWords = {}
for word in wordList:
for i in range(len(word)):
wildcard = self.getWildcard(word, i)
if wildcard in wildcardToWords:
wildcardToWords[wildcard].append(word)
else:
wildcardToWords[wildcard] = [word]
return wildcardToWords
def ladderLength(self, beginWord, endWord, wordList):
if endWord not in wordList:
return 0
wildcardToWords = self.buildWildcardToWords(wordList)
#seen will ensure if visited or not
seen = set()
#this queue will help to do the bfs traversal
queue = collections.deque([(beginWord, 1)])
while queue:
word, level = queue.popleft()
seen.add(word)
if word == endWord:
return level
for i in range(len(word)):
wildcard = self.getWildcard(word, i)
for nextWord in wildcardToWords.get(wildcard, []):
if nextWord not in seen:
queue.append((nextWord, level + 1))
return 0