class Solution(object): def ladderLength(self, beginWord, endWord, wordList): wordList.add(endWord) queue = collections.deque([[beginWord, 1]]) while queue: word, length = queue.popleft() if word == endWord: return length for i in range(len(word)): for c in 'abcdefghijklmnopqrstuvwxyz': next_word = word[:i] + c + word[i+1:] if next_word in wordList: wordList.remove(next_word) queue.append([next_word, length + 1]) return 0
Nice solution, very similar to mine, but you should first process wordList and get the neighboring words in O(1) and save much, much time.
Check out my solution at https://leetcode.com/discuss/98667/simple-understand-python-solution-using-preprocessing-beats
This should be upvoted more. So concise and easy to understand. The top voted answers are so complicated IMHO.
@agave At the expense of a large dictionary you created + a visited set
@sylvanyang since it's BFS, going deeper level by level. So the very first word == endword will return the shortest length.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.