[Python] Leetcode word ladder : How is this solution most efficient?

I'm doing this question in Leetcode :

https://leetcode.com/problems/word-ladder/

My solution was a BFA approach, and only one nested loop:

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


Here is the most efficient solution :

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


Now notonly is this solution O(n4), but also, much more comparisons are going on, with 26 combinations being checked for each word. Can someone explain how this is a more optimized code?

Btw, I'm a bit new to competitive programming.

Continue reading...