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 defaultdict
class 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