Leetcode word ladder : How is this solution most efficient?

Question

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[i] != s2[i]:
            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.

Answer 1

Not an expert, but I notice that the 'efficient solution' is using sets which are hashed entries unlike lists. Being hashed indexed, sets are typically O(1) when used for checking if entry exists (as compared to iterating). While lists are O(n) for checking existence.

I did notice an interesting optimization in the 'efficient solution' which is to flip the search direction to which ever has the least 'starting' words to search. Note the "ends" variable is set and not just a string. For example, first time through there is 1 word in the start set and 1 word in the end set, but after going through the 1 start word, it identifies 5 words that vary by 1 letter and become the new start word set (with the level count incrementing by 1). Theoretically you now need to chase down each of those words, and some are going to be red herrings. HOWEVER, before doing the next level down search, the algorithm will swap the end set for the start set if the end set is smaller. Thereby reducing or eliminating red herrings. So for the 2nd iteration, the end set has 1 word, and the start set has 5 words, so it swaps them. This comparison is done at end of each level search.