LeetCode Word Ladder: Как это решение наиболее эффективно? ⇐ Python

[Anonymous]

Я задаю этот вопрос в LeetCode:
https://leetcode.com/problems/word-ladder/образное/> Моим решением было подход BFA, и только один вложенный цикл:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
ans = 0
visited = set()
n = len(wordList)
seq = [[beginWord,1]]
while (len(seq)!=0):
now,val = seq.pop(0)
if now == endWord:
return val
for st in wordList:
if st in visited:
continue
if self.related(now,st):
seq.append([st,val+1])
visited.add(st)
return 0

def related(self,s1,s2):
n = len(s1)
diff = False
for i in range(n):
if s1 != s2:
if diff:
return False
diff = True
return diff
< /code>
Вот наиболее эффективное решение: < /p>
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
starts = {beginWord}
ends = {endWord}
level = 1
while starts:
level += 1
words -= starts
next_words = set()
for word in starts:
for i in range(len(word)):
left = word[:i]
right = word[i+1:]
for char in string.ascii_lowercase:
next_word = left + char + right
if next_word in words:
if next_word in ends:
return level
next_words.add(next_word)
starts = next_words
if len(starts) > len(ends):
starts, ends = ends, starts
return 0
< /code>
Теперь, как только это решение O (N4), но также и гораздо больше сравнений, с 26 комбинаций, проверяемых на каждое слово. Может ли кто -нибудь объяснить, как это более оптимизированный код?
Кстати, я немного новичок в конкурентном программировании.>

Подробнее здесь: https://stackoverflow.com/questions/684 ... -efficient