performance - Word ladder leetcode

Question

I am working on Word Ladder - LeetCode

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

My Approach:

1. Create a graph with word distances
2. Calculate the distance to the endWord using BFS

Code:

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        
        graph = {}
        wordList = [beginWord] + wordList if beginWord not in wordList else wordList
        for i in range(len(wordList)):
            wordU = wordList[i]
            # Compute distances and prepare a graph when the distance is equal to one
            for j in range(i+1, len(wordList)):
                wordV = wordList[j]

                if wordU not in graph.keys():
                    graph[wordU] = []
                if wordV not in graph.keys():
                    graph[wordV] = []

                if self.word_difference(wordU, wordV) == 1:
                    graph[wordU].append(wordV)
                    graph[wordV].append(wordU)

        visited = set()
        queue = [beginWord]
        distances = {w:1 for w in queue} # since the first word is 1 we are putting 2 here for the root
        return self.BFS(graph, endWord, visited, queue, distances)
    
    def word_difference(self, word1, word2):
        # Compute the difference in words
        distance = 0
        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                distance += 1
        return distance

    def BFS(self, graph, endNode, visited, queue, distances):
        while queue:
            node = queue.pop(0)
            if node not in visited:
                visited.add(node)
            if node == endNode:
                return distances[node]
            for neighbour in graph[node]:
                if neighbour not in visited:
                    visited.add(neighbour)
                    distances[neighbour] = distances[node] + 1
                    queue.append(neighbour)
        return 0

The problem is that the above code is failing on a test case with large word list.

The discussions forum had a solution which took a similar approach but is clearing all the test cases. How can I optimize my solution?

Answer 1

Measure first. If you have a performance problem, make sure you know where it is. A simple, low-tech way to do this is to start throwing time markers into the code and printing the elapsed time for different phases of the work. In your case, the graph-building is the costly part of the process, so there's no need to waste time thinking about how to optimize the BFS code.

from time import time

t1 = time()
...              # Do some work.
t2 = time()
...              # Do some other work
t3 = time()

print('Phase 1', t2 - t1)
print('Phase 2', t3 - t2)

Your algorithm and the one from the discussion forum are quite different. Yes, they both build a graph and then use BFS on it. But, as noted, the performance problem lies in the graph building. Your algorithm is O(N*N): nested loops over wordList. But the other solution is effectively O(N) because the inner loop is over the positions in the current word, not the entire word list.

# Your approach: O(N*N).
for i in range(len(wordList)):
    ...
    for j in range(i+1, len(wordList)):
        ...

# Discussion forum: O(N*m), where m is tiny, effectively a constant.
for word in word_list:
    for i in range(len(word)):
        ...

Too much computation: word difference is not relevant. A clue that your algorithm is inefficient comes from realizing that we don't actually care about word distances. Our goal is to build a graph linking immediate neighbors (those having a difference of exactly 1), but your algorithm does the work of actually computing all pairwise differences.

Invert the strategy: create linking keys. Suppose you realize that you don't need the word differences. The problem becomes, how do we find immediate neighbors (those having a difference of exactly 1) without actually computing any differences? That's not an easy question to answer, of course, and to some extent it requires a leap of insight. Nonetheless, there is still a general lesson to be learned. The wildcard-based strategy in the discussion forum achieves that goal by figuring out a way to map each word to some linking-keys, such that immediate neighbors will share a common key. The way to do that is to convert each word (a sequence of characters) into other sequences of characters where each character gets replaced by a generic value.

# The word
dog

# Its linking keys
_og
d_g
do_