Word Ladder Ii - Leetcode Solution

Problem Statement:

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note:

Return an empty list if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]

Explanation: There are 2 shortest transformation sequences: "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog" Example 2:

Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, so there is no valid transformation sequence.

Approach:

1. Begin by building a dictionary in order to retrieve the list of neighbors for each word from the list of words.
2. In order to find all possible word ladders, we need to use a BFS approach in order to generate all possible word ladders from the beginWord to the endWord.
3. The idea is to start from the beginWord and adding to the queue with the first word in the ladder. Then, we add each of its neighbors to the queue as the second word in the ladder. We continue this process until we reach the endWord.
4. Along with each word, we add its ladder to the queue.
5. We use a visited set to ensure that we don’t visit the same word again.
6. Finally, we return all the possible word ladders.

Solution:

from collections import defaultdict, deque

def findLadders(beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:

# build a dictionary of all possible combinations of words
word_dict = defaultdict(list)

for word in wordList:
    for i in range(len(word)):
        word_dict[word[:i] + "*" + word[i+1:]].append(word)

# perform a BFS to get all possible ladder
visited = set([beginWord])
queue = deque([(beginWord, [beginWord])])
res = []

while queue:
    curr_word, curr_ladder = queue.popleft()
    for i in range(len(curr_word)):
        # find all the words that could be created with the current word
        next_words = word_dict[curr_word[:i] + "*" + curr_word[i+1:]]
        for next_word in next_words:
            if next_word in visited:
                continue
            # if we find the endWord, append the whole ladder to res
            # otherwise, create a new ladder with the current ladder + next_word
            if next_word == endWord:
                res.append(curr_ladder + [next_word])
            else:
                queue.append((next_word, curr_ladder + [next_word]))

            visited.add(next_word)

return res

Time Complexity:

Building the dictionary takes O(NL^2), where N is the number of words and L is the length of the words. This is because we iterate through each character in each word and create a key with the empty space and then we append the word to the value of that key. To find all possible neighbors for a word, it takes O(L^2N), as for each word we iterate over its length and then over the number of words in the dictionary. Performing the BFS algorithm takes O(NL^2) time in the worst case, where we have to process each word in the dictionary once. In each iteration of the algorithm, we generate all possible neighbors of the current word with wildcard queries. A typical query in the dictionary takes O(L) time and we have to query each word, hence O(NL) total query time. Therefore, the time complexity of the algorithm is O(NL^2+NL^2) ~ O(NL^2). Space Complexity:

Creating the dictionary takes up O(NL^2) space in the worst case. In the BFS approach we need to store the visited words in a set, which takes up O(N) space. We also need to store the whole ladder of words in each step of the BFS. Therefore, the space complexity of the algorithm is O(NL^2).

Overall, we have discussed a detailed solution for Word Ladder II problem on LeetCode and analyzed its time and space complexities.

1