# Word Ladder II

## Question ([LC.126](https://leetcode.com/problems/word-ladder-ii/description/))

> 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](/files/-Mghv_sbfVgAjAukk-qQ)

## Analysis 

![finding all shortest paths in a simple graph](/files/-MghviWKmiv_6n_35ZDr)

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 

```python
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&#x20;

Time O(V+E) for bfs then O(V + E) worst case for the dfs&#x20;

Space O(V+E) for visited dict and O(nCr) for the paths&#x20;

## Reference&#x20;

* Stack Overflow - [How do you add a string to a deque without breaking the string up into characters?](https://stackoverflow.com/questions/5888680/how-do-you-add-a-string-to-a-deque-without-breaking-the-string-up-into-character)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/graph-search/graph-theory/graph-traversal/word-ladder-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.