The first intuitive idea that jumps out of my mind after taking a look at LeetCode #127 is using the graph algorithm. But for building the graph first, I need to traverse the wordList by O(n2) times.
Here comes the time complexity analysis: the length of the wordList is about 5000, O(n2) means 5000*5000=25*106. For a python script in LeetCode, it will cost about 1 second for every 106 operations. Thus 25*106 will cost about 25 seconds, which is too long for a LeetCode question.
Therefore the best method to build a graph is not to traverse the wordList multiple times, but to just iterate all lower-case alphabets (be aware of the constraints beginWord, endWord, and wordList[i] consist of lowercase English letters.). By just iterating lower-case alphabets, I can reduce time to 260*5000=1.3*106 (the max length of words in wordList is 10).
The code below also uses my old trick of visited nodes.
from collections import defaultdictclass Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: words_set = set(wordList) conns = defaultdict(set) for word in wordList + [beginWord]: for index in range(len(word)): conns[word] |= {word[:index] + cand + word[index+1:] for cand in "abcdefghijklmnopqrstuvwxyz" if cand != word[index] and word[:index] + cand + word[index+1:] in words_set} # bfs queue = {beginWord} already = set() ans = 1 while queue: new_queue = set() for node in queue: for _next in conns[node]: if _next == endWord: return ans + 1 new_queue.add(_next) already |= queue queue = new_queue - already ans += 1 return 0