# A tip for the time complexity of LeetCode #127

2023-02-17 10:34 浏览: 1022322 次 字号:

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}
ans = 1
while queue:
new_queue = set()
for node in queue:
for _next in conns[node]:
if _next == endWord:
return ans + 1