Day 9 - Word Ladder
Tags: leetcode, python
Published: 2021-01-09 15:57:17

## The Problem

>Given two words `beginWord` and `endWord`, and a dictionary `wordList`, return the length of the shortest transformation sequence from `beginWord` to `endWord`, such that:

> * Only one letter can be changed at a time.
> * Each transformed word must exist in the word list.

>Return `0` if there is no such transformation sequence.

__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.
```

__Constraints:__

* `1 <= beginWord.length <= 100`
* `endWord.length == beginWord.length`
* `1 <= wordList.length <= 5000`
* `wordList[i].length == beginWord.length`
* `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
* `beginWord != endWord`
* All the strings in `wordList` are __unique__.


## My Tests

```python
import pytest
from .Day9 import Solution

s = Solution()


@pytest.mark.parametrize(
    "beginWord,endWord,wordList,expected",
    [
        ("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"], 5),        
        ("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
        ("count", "court", ["mount", "point"], 0),
    ],
)
def test_ladder_length(beginWord, endWord, wordList, expected):
    assert s.ladderLength(beginWord, endWord, wordList) == expected
```

## My Solution

```python
from typing import List, Dict
import collections


def getLadderLength(
    queue,
    visited: Dict[str, int],
    otherVisited: Dict[str, int],
    wordLength: int,
    combos: Dict[str, List[str]],
):
    word, level = queue.popleft()
    for i in range(wordLength):
        testWord = word[:i] + "*" + word[i + 1 :]
        if testWord in combos:
            for w in combos[testWord]:
                if w in otherVisited:
                    return level + otherVisited[w]
                if w not in visited:
                    visited[w] = level + 1
                    queue.append((w, level + 1))
    return 0


def preProcessNeighbors(wordList: List[str], wordLength: int):
    combos = {}
    for word in wordList:
        for i in range(wordLength):
            testWord = word[:i] + "*" + word[i + 1 :]
            if testWord not in combos:
                combos[testWord] = []
            combos[testWord].append(word)
    return combos


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        wl = len(beginWord)
        combos = preProcessNeighbors(wordList, wl)

        qBegin = collections.deque([(beginWord, 1)])
        qEnd = collections.deque([(endWord, 1)])

        visitedBegin = {beginWord: 1}
        visitedEnd = {endWord: 1}
        ladderLength = 0

        while qBegin and qEnd:
            ladderLength = getLadderLength(qBegin, visitedBegin, visitedEnd, wl, combos)
            if ladderLength > 0:
                return ladderLength
            ladderLength = getLadderLength(qEnd, visitedEnd, visitedBegin, wl, combos)
            if ladderLength > 0:
                return ladderLength

        return 0
```

## Analysis

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/0abvnv1ie2oobqqp9o7f.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/f4qtqz3relt3k9o5kww6.png)

## My Commentary

After doing this one I am currently experiencing a high level of hate for coding problems. I had actually solved a problem similar to this some time ago so I even had the benefit of working from memory in some aspects but it still drove me a little crazy. 

Looking at the problem we know we need to create a path of words going from the `beginWord` to the `endWord`. Looking at the example it might be intuitive at first to imagine iterating over the list, check which words differ by one letter, count the transformations along the way. That quickly breaks down once you change the example to be a little more complex. My next intuition was to maybe have a map of the various paths and return the shortest. That would get way too messy though. What would you use as a key? Do you have to access every list too often?

If we need a path and we need to track path length then the data structure we need is clearly a graph. Each node is a word with the level the node is on the path between beginning and end. Each neighbour of a node must contain another word that differs by only one letter. That way we adhere to the requirement that each transformation changes only one letter. 

The first thing we do is check if the `endWord` is in the list at all and return `0` if not. 

Then we must preprocess the graph.

```python
def preProcessNeighbors(wordList: List[str], wordLength: int):
    combos = {}
    for word in wordList:
        for i in range(wordLength):
            testWord = word[:i] + "*" + word[i + 1 :]
            if testWord not in combos:
                combos[testWord] = []
            combos[testWord].append(word)
    return combos
```

`wordLength` is pretty much a constant based on the constraints: 

* `endWord.length == beginWord.length`
* `wordList[i].length == beginWord.length`

We iterate over every word in our word list. Then we generate versions of the word replacing each letter with a `*`. So for example, say the word is `can`. We generate 3 words: `*an`, `c*n`, `ca*`. We are going to use these as keys and create a data structure that looks like this:

```json
{
  "*an": ["can"],
  "c*n": ["can"],
  "ca*": ["can"]
}
```

What use is this?

Imagine we have a word list like this:

```
["hot", "dot", "dog", "cog"]
```

If we use the preprocessing above we will end up with a data structure like this:

```json
{
  "*ot": ["hot", "dot"],
  "h*t": ["hot"],
  "ho*": ["hot"],
  "d*t": ["dot"],
  "do*": ["dot", "dog"],
  "*og": ["dog", "cog"],
  "c*g": ["cog"],
  "co*": ["cog"]
}
```

This will come in pretty handy when we're trying to figure out the transformations. 

Next step is to set up 2 queues to allow us to do [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) to find the shortest path. In my solution, I am initiating a search from both the beginning and the end. Honestly, it would not have occurred to me to do it that way except I have come across a problem like this before and saw this as a form of optimisation. I did try with and without this i.e. also doing the search only from the start. In the leetcode analysis, there wasn't really much different but I am using the dual search since that's what I learned and it doesn't make it much more complicated.

So next step, setup 2 queues and 2 maps to track visited words (you can replace this with one to only traverse one way):

```python
qBegin = collections.deque([(beginWord, 1)])
qEnd = collections.deque([(endWord, 1)])

visitedBegin = {beginWord: 1}
visitedEnd = {endWord: 1}
```

Traverse the queues using a while loop with `popleft`:

```python
while qBegin and qEnd:            
```

Get the word and the current level in the queue:

```python
word, level = queue.popleft()
```

Iterate over each letter in that word and generate the keys to use in that map we preprocessed earlier:

```python
word, level = queue.popleft()
    for i in range(wordLength):
        testWord = word[:i] + "*" + word[i + 1 :]
```

Now we check that map e.g. if we generated a word like "*ot", based on our example earlier, we'd get back a list like: `["hot", "dot"]`

Recall:

```json
{
  "*ot": ["hot", "dot"],
  etc...
}
```

So in the following code:

```python
if testWord in combos:
            for w in combos[testWord]:
                if w in otherVisited:
                    return level + otherVisited[w]
                if w not in visited:
                    visited[w] = level + 1
                    queue.append((w, level + 1))
```

We would iterate over that list. If we discovered that word had already been visited in the other search, we would know that is was part of the path and we would have our answer `return level + otherVisited[w]`.

If it was not visited, we would mark it as visited on this end `visited[w] = level + 1` and add the word to the queue `queue.append((w, level + 1))` and continue the search.

The time complexity here is basically the length of every word squared multiplied by the number of words. So if N is the number of word sand K is word length, we'd have:

O(K^2 * N)

The space complexity is basically the same. We stored K^2 * N in that map. 

My solution here is not great I think. The coded is messy and the performance could certainly be optimised a lot more (only beat 50% of other submissions). Other things bother me like the method name I used `getLadderLength` doesn't make sense but my brain is fried at this point so leaving it here. I hope I don't ever get one like this in an interview!