Day 9 - Word Ladder

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

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

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

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.

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:

{
  "*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:

{
  "*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 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):

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:

while qBegin and qEnd:            

Get the word and the current level in the queue:

word, level = queue.popleft()

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

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:

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

So in the following code:

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!