Advertisement
smj007

Untitled

Feb 12th, 2024 (edited)
2,063
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.06 KB | None | 0 0
  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)
  19.         visited.add(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)
  34.                             visited.add(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:
  65.                             visit.add(neiWord)
  66.                             q.append(neiWord)
  67.             res += 1
  68.         return 0
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement