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

In this problem we need to find shortest distance between two words, so the first idea you should think is classical bfs.

  1. Let m be length of each word and n be total number of words.
  2. Let us also add beginWord to our list of words and create words_inverse: connections between words and their numbers.
  3. Now, time to create words_graph. It can be done in the following way: iterate over each word and each place and find all possible neighbors for each word: for example for word apple, we have: apple, bpple, cpple, ... zpple, aaple, abple,... azple, ..., appla, applb, ... applz. In words_graph we will keep connections between indexes of words.
  4. Run classical bfs for created graph, using deque: first, we mark all distances as -1 and 0 for endWord. Then we extract left element fro queue, check if it is what we are looking for and if it is, we return distance. If it is not, then we visit all neighbors and if they are not visited yet, we add them to queue.

Complexity: time complexity is O(26nm^2), because for each of n words we need to check all 26m neighbours and each comparison of words is O(m). Also we have bfs step, where we have graph on m nodes with at most 26n neighbours for each node, so traverse of this graph will be O(26mn), which is less than previous term. Space complexity is O(26mn).

Note, that there is alternative way to create our graph: we can check each pair of words and we will have O(mn^2) time to create it. This method is preferable if m*n*n < 26*n*m*m, the is if n < 26m.

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        wordList.append(beginWord)
        m, n = len(wordList[0]), len(wordList)
        words_inverse = {w:i for i, w in enumerate(wordList)}
        
        words_graph = defaultdict(set)
        alphabet = "abcdefghijklmnopqrstuvwxyz"

        if endWord not in words_inverse: return 0
        end_ind = words_inverse[endWord]

        for word in wordList:
            for l in range(m):
                p1, p2 = word[0:l], word[l+1:]
                for i in alphabet:
                    tmp = p1 + i + p2
                    if tmp in words_inverse and tmp != word:
                        words_graph[words_inverse[word]].add(words_inverse[tmp])

        depths = [-1] * (n-1) + [0]
        queue = deque([n-1])

        while queue:
            curr = queue.popleft()
            if curr == end_ind:
                return depths[end_ind]  + 1
            for neib in words_graph[curr]:
                if depths[neib] == -1:
                    queue.append(neib)
                    depths[neib] = depths[curr] + 1
                    
        return 0

If you like the solution, you can upvote it on leetcode discussion section: Problem 0127