-
Notifications
You must be signed in to change notification settings - Fork 0
/
127.word-ladder.py
36 lines (32 loc) · 1.04 KB
/
127.word-ladder.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
#
# @lc app=leetcode id=127 lang=python3
#
# [127] Word Ladder
#
from lcimports import *
# @lc code=start
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
neighbours = defaultdict(list)
wordList.append(beginWord)
for word in wordList:
for i in range(len(word)):
pattern = word[:i] + '*' + word[i+1:]
neighbours[pattern].append(word)
visited = set()
visited.add(beginWord)
q = [(beginWord, 1)]
while q:
curr, chain = q.pop(0)
for i in range(len(curr)):
pattern = curr[:i] + '*' + curr[i+1:]
for word in neighbours[pattern]:
if word == endWord:
return chain + 1
if word not in visited:
visited.add(word)
q.append((word, chain + 1))
return 0
# @lc code=end