endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Company Tags: Google, Amazon

Core Concept: Graph, BFS

Solve on LeetCode

7c:T439,from collections import deque, defaultdict class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if endWord not in wordList: return 0 # Optimization: use a set for O(1) lookups wordSet = set(wordList) wordSet.add(beginWord) nei = defaultdict(list) for word in wordSet: for j in range(len(word)): pattern = word[:j] + "*" + word[j + 1 :] nei[pattern].append(word) visit = {beginWord} q = deque([beginWord]) res = 1 while q: for i in range(len(q)): word = q.popleft() if word == endWord: return res for j in range(len(word)): pattern = word[:j] + "*" + word[j + 1 :] for neiWord in nei[pattern]: if neiWord not in visit: visit.add(neiWord) q.append(neiWord) res += 1 return 07d:T469,class Solution { public: int ladderLength(string beginWord, string endWord, vector& wordList) { unordered_set wordSet(wordList.begin(), wordList.end()); if (wordSet.find(endWord) == wordSet.end()) { return 0; } queue q; q.push(beginWord); int res = 1; while (!q.empty()) { int q_len = q.size(); for (int i = 0; i <

Hand of Straights (#846)

View Hints

View Solution