Word Ladder

Patrick Leaton
Published: July 26, 2021, 7:28 a.m.
Problem Description

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

 

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

 

Constraints:

  • 1 <= beginWord.length <= 10
  • 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 words in wordList are unique.

 

The description was taken from https://leetcode.com/problems/word-ladder/.

Problem Solution

#O(M^2*N) Time, O(M^2*N) Space
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
       
        adjacency, seen = {}, {}
        wordList.append(beginWord)
       
        for word in wordList:
            for char in range(0, len(word)):
                node = word[:char] + "*" + word[char+1:]
                if node not in adjacency:
                    adjacency[node] = [word]
                else:
                    adjacency[node].append(word)
       
        def bfs(beginWord):
            queue = collections.deque([beginWord])
            seen[beginWord] = True
            output = 1
            while queue:
                width = len(queue)
                for _ in range(0, width):
                    word = queue.popleft()
                    if word == endWord:
                        return output
                    for i in range(0, len(word)):
                        node = word[:i] + "*" + word[i+1:]
                        for neighbor in adjacency[node]:
                            if neighbor not in seen:
                                seen[neighbor] = True
                                queue.append(neighbor)
                output += 1
            return 0
       
        return bfs(beginWord)

Problem Explanation

Since adjacent words will differ by one letter, we can test each word's similarity excluding that letter.  If we do that, they should be the same.

We can first go through each character of each word within the wordlist and make multiple nodes from the word which will be the word excluding the character that is in the current iteration.  We will then map the adjacency of that node to the word.

Since we are making a list of adjacent words that we will need to iterate through, that is an indication that a Breadth-First Search can be used.  A word node will have multiple neighbor words that we will want to explore before moving onto the next word node in a BFS manner.

While doing a BFS on the list of adjacent nodes, we will count the node levels in the BFS path from the beginning word to the ending word, using the adjacent nodes from the list we made.

However many levels we traversed are the shortest transformation sequence.

First off, if the ending word isn't in the word list then we will have no path to get there.  If that is the case, we will return zero and be done.

        if endWord not in wordList:
            return 0

 

Otherwise, we will create an adjacency list and a list of nodes we've seen during our BFS, both initialized to empty hashmaps.

        adjacency, seen = {}, {}

 

We'll also append the beginning word to the wordlist since it isn't in there.

        wordList.append(beginWord)

 

Next, we will iterate through each character of each word in the wordlist.

        for word in wordList:
            for char in range(0, len(word)):

 

While doing that, we will make a word node that is the word excluding the character in the current iteration, so that two words that are the same without this character will be the same word with this asterisk taking the character's place.  

                node = word[:char] + "*" + word[char+1:]

 

We will then map the adjacency of the word node with the asterisk to the original word.

                if node not in adjacency:
                    adjacency[node] = [word]
                else:
                    adjacency[node].append(word)

The shortest transformation subsequence is going to be a BFS because each node in the adjacency list can map to multiple nodes.  We will want to first traverse the layer of all of those nodes because each layer is going to be one character difference, meaning it will be one transformation.  That means each BFS iteration will take one additional transformation subsequence.

                hit     1
                /   
            hot        2
           /     \    
        dot    lot      3
      /             \      
  dog           log    4
   /                  \
cog                cog     5

Let's start building our bfs function.

It will take a beginWord variable as the root node.

        def bfs(beginWord):

 

We will take that root node and initialize our queue with it, mark it as seen, and initialize the output to one.

            queue = collections.deque([beginWord])
            seen[beginWord] = True
            output = 1

 

While the queue still has nodes in it, we will continue to process them.

            while queue:

 

Each iteration will start by us calculating the width of the current layer within the queue.  This will be important since we will need to know how many nodes we need to process before we finish searching the layer.

                width = len(queue)

 

Then, for each word in that layer, we will pop it off the list and see if it is the ending word.  If it is, we will return the level count it took to get here.

                for _ in range(0, width):
                    word = queue.popleft()
                    if word == endWord:
                        return output

 

If it is not the ending word, we will still process it.

Same as we did when building the adjacency list, we will iterate through each character in the word and we will make a word node that is the word excluding the character in the current iteration so that two words that are the same without this character will be the same node.

                    for i in range(0, len(word)):
                        node = word[:i] + "*" + word[i+1:]

 

For each of those word nodes we make, we will grab their neighbors which are the words that are the same excluding the current character, and add them to the next layer in the BFS.

                        for neighbor in adjacency[node]:
                            if neighbor not in seen:
                                seen[neighbor] = True
                                queue.append(neighbor)

 

Once we have grabbed each word from the queue, made different word nodes for the number of characters in the word, and then placed each adjacent word to those word nodes into the queue, we have finished another transformation sequence iteration so we will increment our output by one.

                output += 1

 

If we never got to the point where we popped the ending word from our queue, meaning we never found a path to it, we will return zero.

            return 0

Now that our BFS function is built, we just need to pass the root node, which is the first word.

         return bfs(beginWord)