Solution
from collections import deque
from typing import List
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
q = deque([beginWord])
ans = 1
while q:
ans += 1
for _ in range(len(q)):
s = q.popleft()
s_list = list(s)
for i in range(len(s_list)):
origin = s_list[i]
for j in range(26):
s_list[i] = chr(ord('a') + j)
t = ''.join(s_list)
if t not in words:
continue
if t == endWord:
return ans
q.append(t)
words.remove(t)
s_list[i] = origin
return 0
# 本地测试
if __name__ == "__main__":
sol = Solution()
print(sol.ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"]))
# 预期输出：5
Solution 2
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
def extend(m1, m2, q):
for _ in range(len(q)):
s = q.popleft()
step = m1[s]
s = list(s)
for i in range(len(s)):
ch = s[i]
for j in range(26):
s[i] = chr(ord('a') + j)
t = ''.join(s)
if t in m1 or t not in words:
continue
if t in m2:
return step + 1 + m2[t]
m1[t] = step + 1
q.append(t)
s[i] = ch
return -1
words = set(wordList)
if endWord not in words:
return 0
q1, q2 = deque([beginWord]), deque([endWord])
m1, m2 = {beginWord: 0}, {endWord: 0}
while q1 and q2:
t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2)
if t != -1:
return t + 1
return 0