Word Ladder II

Question (LC.126)

Given a beginWord and an endWord, find all shortest transformation sequences from beginWord to endWord.

Example

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

I: beginWord = "red", endWord = "tax", wordList = ['ted', 'tex', 'red', 'tax', 'tad', 'den', 'rex', 'bee']
O: [['red', 'ted', 'tad', 'tax'], ['red', 'ted', 'tex', 'tax'], ['red', 'rex', 'tex', 'tax']]

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

simple example with multiple shortest paths

Analysis

finding all shortest paths in a simple graph

A simple BFS is not enough to find all shortest paths because you simply do not know which one is the shortest one yet.

This question is essentially finding all shortest paths in a simple graph.

The first step is to build a visited map where each node stores the shortest distance to arrive and a list of nodes that can get there with that distance.

A: []
B: [1: A]
C: [1: A]
D: [1: A]
E: [2: B, D]
F: [2: C]
G: [3: E, F]

The second step is to find all possible combinations from the visited map.

G -> E -> B -> A
G -> E -> D -> A
G -> F -> C -> A

Code

from collections import deque 

class Solution:

    def _next_key(self, current_word: str) -> Iterable[str]:
        for i in range(len(current_word)):
            yield current_word[:i] + '*' + current_word[i + 1:]

    def _construct_dict_graph(self, word_list: List[str]) -> Dict[str, List[str]]:

        dict_graph: Dict[str, List[str]] = defaultdict(list)

        for word in word_list:
            for search_key in self._next_key(word):
                dict_graph[search_key].append(word)

        return dict_graph

    def _visitedDict(
        self, 
        beginWord: str, 
        endWord: str, 
        dict_graph: Dict[str, List[str]]
    ) -> Dict[str, Tuple[int, List[str]]]:

        queue: Deque[str] = deque()
        visited_dict: Dict[str, Tuple[int, List[str]]] = {}

        queue.append(beginWord)
        visited_dict[beginWord] = (0, [])

        depth = 1

        while len(queue) > 0:
            breadth = len(queue)
            for i in range(breadth):
                current_word = queue.popleft()
                # use the dictionary key and to see if the distance is shorter
                # because you want to get to that node with the shortest distance
                for search_key in self._next_key(current_word):
                    for next_word in dict_graph[search_key]:
                        if next_word in visited_dict and visited_dict[next_word][0] < depth:
                            continue
                        # the writes going to the queue are different from what going to 
                        # the visited dict has all previous paths
                        # queue only has where to visit next
                        if next_word not in visited_dict:
                            visited_dict[next_word] = (depth, [current_word])
                            queue.append(next_word)
                        else:
                            visited_dict[next_word][1].append(current_word)
                        
            depth += 1

        return visited_dict
    
    def _findCombinations(
            self,
            current_word: str,
            stop_word: str,
            visited_dict: Dict[str, Tuple[int, List[str]]],
            current_list: Deque[str],
            results: List[List[str]]
    ) -> None:

        if current_word not in visited_dict:
            return

        if current_word == stop_word:
            results.append(list(current_list))
            return

        for word in visited_dict[current_word][1]:
            current_list.appendleft(word)
            self._findCombinations(word, stop_word, visited_dict, current_list, results)
            current_list.popleft()
    
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        if beginWord == endWord:
            return [[beginWord]]

        if endWord not in wordList:
            return []

        dict_graph = self._construct_dict_graph(wordList)
        visited_dict = self._visitedDict(beginWord, endWord, dict_graph)
        results = []
        current_list = deque()
        current_list.appendleft(endWord)
        self._findCombinations(endWord, beginWord, visited_dict, current_list, results)
        return results

Complexity

Time O(V+E) for bfs then O(V + E) worst case for the dfs

Space O(V+E) for visited dict and O(nCr) for the paths

Reference

• Stack Overflow - How do you add a string to a deque without breaking the string up into characters?