# Untitled

Feb 12th, 2024 (edited)
2,063
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # mine
2. class Solution:
3.     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
4.
5.         wordList.append(beginWord)
6.         from collections import defaultdict
7.         mapping = defaultdict(list)
8.
9.         for word in wordList:
10.             for j in range(len(word)):
11.                 pattern = word[:j] + "*" + word[j+1:]
12.                 mapping[pattern].append(word)
13.
14.
15.         from collections import deque
16.         q = deque()
17.         visited = set()
18.         q.append(word)
20.         res = 1
21.
22.         while q:
23.             if endWord in q:
24.                 return res
25.
26.             for i in range(len(q)):
27.                 word = q.popleft()
28.
29.                 for j in range(len(word)):
30.                     pattern = word[:j] + "*" + word[j+1:]
31.                     for neighbour in mapping[pattern]:
32.                         if neighbour not in visited:
33.                             q.append(neighbour)
35.             res += 1
36.
37.         return 0
38.
39.
40. # neetcode
41. class Solution:
42.     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
43.         if endWord not in wordList:
44.             return 0
45.
46.         nei = collections.defaultdict(list)
47.         wordList.append(beginWord)
48.         for word in wordList:
49.             for j in range(len(word)):
50.                 pattern = word[:j] + "*" + word[j + 1 :]
51.                 nei[pattern].append(word)
52.
53.         visit = set([beginWord])
54.         q = deque([beginWord])
55.         res = 1
56.         while q:
57.             for i in range(len(q)):
58.                 word = q.popleft()
59.                 if word == endWord:
60.                     return res
61.                 for j in range(len(word)):
62.                     pattern = word[:j] + "*" + word[j + 1 :]
63.                     for neiWord in nei[pattern]:
64.                         if neiWord not in visit: