© Warren Keelan

LeetCode 127. Word Ladder

LeetCode Notes [24]: Java/Kotlin BFS

Problem

Word Ladder - LeetCode

Approach 1: Breadth First Search

Intuition

Start from beginWord and search the endWord using BFS.

Algorithm

1. Do the pre-processing on the given wordList and find all the possible generic/intermediate states. Save these intermediate states in a dictionary with key as the intermediate word and value as the list of words which have the same intermediate word.
2. Push a tuple containing the beginWord and 1 in a queue. The 1 represents the level number of a node. We have to return the level of the endNode as that would represent the shortest sequence/distance from the beginWord.
3. To prevent cycles, use a visited dictionary.
4. While the queue has elements, get the front element of the queue. Let’s call this word as word.
5. Find all the generic transformations of the current_word and find out if any of these transformations is also a transformation of other words in the word list. This is achieved by checking the words.
6. The list of words we get from words are all the words which have a common intermediate state with the word. These new set of words will be the adjacent nodes/words to word and hence added to the queue.
7. Hence, for each word in this list of intermediate words, append (nextWord, level + 1) into the queue where level is the level for the word.
8. Eventually if you reach the desired word, its level would represent the shortest transformation sequence length.

Termination condition for standard BFS is finding the end word.

Java Implementation

import java.util.*;

class Solution {
    class Pair<T1, T2> {
        T1 first;
        T2 second;

        public Pair(T1 first, T2 second) {
            this.first = first;
            this.second = second;
        }
    }

    HashMap<String, List<Integer>> words = new HashMap<>();

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        processWords(wordList);
        Queue<Pair<Integer, Integer>> Q = new LinkedList<>();
        HashMap<Integer, Boolean> visited = new HashMap<>();

        Q.offer(new Pair<>(-1, 1));
        while (!Q.isEmpty()) {
            Pair<Integer, Integer> node = Q.poll();
            Integer index = node.first;
            Integer level = node.second;
            if (!visited.containsKey(index)) {
                visited.put(index, true);
                String word = (index == -1) ? beginWord : wordList.get(index);
                if (Objects.equals(word, endWord)) return level;
                checkWords(word, level, Q);
            }
        }
        return 0;
    }

    public void checkWords(String word, int level, Queue<Pair<Integer, Integer>> Q) {
        for (int j = 0; j < word.length(); j++) {
            String variation = word.substring(0, j) + "-" + word.substring(j + 1);
            List<Integer> wordVariations = words.getOrDefault(variation, new ArrayList<>());
            for (Integer candidateIndex : wordVariations) {
                Q.offer(new Pair<>(candidateIndex, level + 1));
            }
        }
    }

    public void processWords(List<String> wordList) {
        for (int i = 0; i < wordList.size(); i++) {
            String word = wordList.get(i);
            for (int j = 0; j < word.length(); j++) {
                String variation = word.substring(0, j) + "-" + word.substring(j + 1);
                List<Integer> wordIndexes = words.getOrDefault(variation, new ArrayList<>());
                wordIndexes.add(i);
                words.put(variation, wordIndexes);
            }
        }
    }
}

Kotlin Implementation

class Solution {
    fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        val words = buildWords(wordList)
        val queue: Queue<Pair<String, Int>> = LinkedList()
        val visited = mutableSetOf<String>()
        queue.offer(beginWord to 1)
        visited.add(beginWord)
        while (queue.isNotEmpty()) {
            for (j in queue.indices) {
                val (word, depth) = queue.poll()
                if (word == endWord) return depth
                for (i in word.indices) {
                    val variation = word.substring(0, i) + "-" + word.substring(i + 1, word.length)
                    words[variation]?.let { list ->
                        list.forEach { nextWord ->
                            if (!visited.contains(nextWord)) {
                                visited.add(nextWord)
                                queue.offer(nextWord to depth + 1)
                            }
                        }
                    }
                }

            }
        }
        return 0
    }

    private fun buildWords(wordList: List<String>): Map<String, List<String>> {
        val map = mutableMapOf<String, List<String>>()
        wordList.forEach { word ->
            map.putIfAbsent(word, emptyList())
            for (i in word.indices) {
                val variation = word.substring(0, i) + "-" + word.substring(i + 1, word.length)
                map[variation] = (map[variation]?.toMutableList() ?: mutableListOf()) + word
            }
        }
        return map
    }
}

Complexity Analysis

Time Complexity: O(L²×N), where L is the length of each word and N is the total number of words in the input word list.

• For each word in the word list, we iterate over its length to find all the intermediate words corresponding to it. Since the length of each word is L and we have N words, the total number of iterations the algorithm takes to create words is L×N. Additionally, forming each of the intermediate word takes O(L) time because of the substring operation used to create the new string. This adds up to a complexity of O(L²×N).
• Breadth first search in the worst case might go to each of the N words. For each word, we need to examine L possible intermediate words/combinations. Notice, we have used the substring operation to find each of the combination. Thus, L combinations take O(L²) time. As a result, the time complexity of BFS traversal would also be O(L²×N).
• Combining the above steps, the overall time complexity of this approach is O(L²×N).

Space Complexity: O(L×N)

• Each word in the word list would have L intermediate combinations. To create the words HashMap we save an intermediate word as the key and the indices corresponding to each original word as the value. Note, for each of L intermediate words we save the indices corresponding to each original word. This simply means, for every word we would need a space of L to save all the transformations corresponding to it. Thus, words would need a total space of O(L×N).
• Visited dictionary would need a space of O(N).
• Queue for BFS in worst case would need a space for all O(N) words.
• Combining the above steps, the overall space complexity is O(L×N) + O(N) + O(N) = O(L×N) space.

Approach 2: Bidirectional Breadth First Search

Intuition

The graph formed from the nodes in the dictionary might be too big. The search space considered by the breadth first search algorithm depends upon the branching factor of the nodes at each level. If the branching factor remains the same for all the nodes, the search space increases exponentially along with the number of levels. Consider a simple example of a binary tree. With each passing level in a complete binary tree, the number of nodes increase in powers of 2.

We can considerably cut down the search space of the standard breadth first search algorithm if we launch two simultaneous BFS. One from the beginWord and one from the endWord. We progress one node at a time from both sides and at any point in time if we find a common node in both the searches, we stop the search. This is known as bidirectional BFS and it considerably cuts down on the search space and hence reduces the time and space complexity.

Algorithm

1. The algorithm is very similar to the standard BFS based approach we saw earlier.
2. The only difference is we now do BFS starting two nodes instead of one. This also changes the termination condition of our search.
3. We now have two visited dictionaries to keep track of nodes visited from the search starting at the respective ends.
4. If we ever find a node/word which is in the visited dictionary of the parallel search we terminate our search, since we have found the meet point of this bidirectional search. It’s more like meeting in the middle instead of going all the way through.
5. The shortest transformation sequence is the sum of levels of the meet point node from both the ends. Thus, for every visited node we save its level as value in the visited dictionary.

Termination condition for bidirectional search is finding a word which is already been seen by the parallel search.

Implementation

class Solution {
        fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        val words = buildWords(wordList)
        val queue1: Queue<Pair<String, Int>> = LinkedList()
        val visited1 = mutableMapOf<String, Int>()
        queue1.offer(beginWord to 1)
        visited1[beginWord] = 1

        val queue2: Queue<Pair<String, Int>> = LinkedList()
        val visited2 = mutableMapOf<String, Int>()
        if (wordList.contains(endWord)) {
            queue2.offer(endWord to 1)
            visited2[endWord] = 1
        }

        while (queue1.isNotEmpty() || queue2.isNotEmpty()) {
            for (j in queue1.indices) {
                val (word, depth) = queue1.poll()
                if (visited2.contains(word)) return depth + visited2[word]!!
                for (i in word.indices) {
                    val variation = word.substring(0, i) + "-" + word.substring(i + 1, word.length)
                    words[variation]?.let { list ->
                        list.forEach { nextWord ->
                            if (!visited1.contains(nextWord)) {
                                queue1.offer(nextWord to depth + 1)
                                visited1[nextWord] = depth
                            }
                        }
                    }
                }
            }

            for (j in queue2.indices) {
                val (word, depth) = queue2.poll()
                if (visited1.contains(word)) return depth + visited1[word]!!
                for (i in word.indices) {
                    val variation = word.substring(0, i) + "-" + word.substring(i + 1, word.length)
                    words[variation]?.let { list ->
                        list.forEach { nextWord ->
                            if (!visited2.contains(nextWord)) {
                                queue2.offer(nextWord to depth + 1)
                                visited2[nextWord] = depth
                            }
                        }
                    }
                }
            }
        }
        return 0
    }

    private fun buildWords(wordList: List<String>): Map<String, List<String>> {
        val map = mutableMapOf<String, List<String>>()
        wordList.forEach { word ->
            map.putIfAbsent(word, emptyList())
            for (i in word.indices) {
                val variation = word.substring(0, i) + "-" + word.substring(i + 1, word.length)
                map[variation] = (map[variation]?.toMutableList() ?: mutableListOf()) + word
            }
        }
        return map
    }
}

Complexity Analysis

Time Complexity: O(L²×N), where L is the length of each word and N is the total number of words in the input word list.

• Similar to one directional, bidirectional also takes O(M2×N)O({M}² \times N)O(M2×N) time for finding out all the transformations. But the search time reduces to half, since the two parallel searches meet somewhere in the middle.

Space Complexity: O(L²×N)

• To store all L transformations for each of the N words in the words dictionary, same as one directional. But bidirectional reduces the search space. It narrows down because of meeting in the middle.

Similar Questions

LeetCode 28. 433. Minimum Genetic Mutation

LeetCode 2452. Words Within Two Edits of Dictionary

Reference

https://leetcode.com/problems/word-ladder/solutions/239223/word-ladder/