Word Ladder II In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of HTML code highlighted in vibrant colors on a computer monitor.

Problem: Word Ladder II

Problem Statement:

Given two words, beginWord and endWord, and a dictionary wordList, find all shortest transformation sequences from beginWord to endWord, such that:

  • Each transformed word must exist in the word list.
  • Only one letter can be changed at a time.
  • Each sequence must be the shortest transformation sequence.

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"]]

Example 2:

Input:

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

Output:

[]

Explanation: There is no possible transformation sequence from hit to cog because the word cog is not in the word list.

Approach:

The problem is essentially about finding the shortest paths in an unweighted graph, where each word is a node, and an edge exists between two nodes if one can be obtained by changing exactly one character.

We can break the solution down into two major steps:

  1. Breadth-First Search (BFS) to find the shortest path.
  2. Backtracking to generate all possible paths once the BFS completes.

Step 1: Breadth-First Search (BFS)

  • BFS is ideal for finding the shortest path in an unweighted graph.
  • We start from beginWord and explore all possible transformations to other words, maintaining the depth of exploration to ensure we only explore the shortest paths.

Step 2: Backtracking

  • Once BFS completes, we need to backtrack from the endWord to beginWord to collect all possible paths that form the shortest transformation sequence.

Time Complexity:

  • Time Complexity: O(N * M * 26), where N is the number of words in the dictionary and M is the length of each word. This is due to generating all possible neighbors for each word.
  • Space Complexity: O(N * M), where N is the number of words in the dictionary and M is the length of each word, due to storage for the BFS queue and path backtracking.

Algorithm:

  1. BFS to determine the shortest distance from beginWord to endWord.
  2. Once BFS is complete, Backtrack from endWord to beginWord to collect all possible shortest paths.

Code Implementation:

1. Python Code

from collections import deque, defaultdict

def findLadders(beginWord, endWord, wordList):
    # Step 1: Edge case - If endWord is not in wordList, return an empty list.
    if endWord not in wordList:
        return []

    # Step 2: Build a dictionary of all possible intermediate words
    wordList.add(beginWord)
    neighbors = defaultdict(list)
    for word in wordList:
        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]
            neighbors[pattern].append(word)

    # Step 3: BFS to find the shortest path length
    level = {beginWord: [[beginWord]]}  # Map to keep track of paths
    queue = deque([beginWord])
    found = False

    while queue and not found:
        visited = set()  # Keep track of words visited in this level
        for _ in range(len(queue)):
            word = queue.popleft()
            for i in range(len(word)):
                pattern = word[:i] + '*' + word[i+1:]
                for neighbor in neighbors[pattern]:
                    if neighbor not in level:
                        level[neighbor] = []
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
                    # Add the new word to all the possible paths
                    if neighbor == endWord:
                        found = True
                    for path in level[word]:
                        level[neighbor].append(path + [neighbor])

        # Move to the next level, after exploring all nodes for the current level
        for word in visited:
            level[word] = [path for path in level[word] if path[-1] == word]

    # Step 4: Return the result
    return level[endWord]

# Example test case
beginWord = "hit"
endWord = "cog"
wordList = {"hot", "dot", "dog", "lot", "log", "cog"}
result = findLadders(beginWord, endWord, wordList)
print(result)

Explanation of the Python Code:

  1. wordList as a set: We convert the word list into a set for fast lookup.
  2. Pattern creation: We create a pattern for each word by replacing one character at a time with *. For example, “hot” becomes *ot, h*t, ho*. This helps in finding all possible neighbors of a word in the graph.
  3. BFS Search: We use BFS to find all the shortest paths from beginWord to endWord.
  4. Backtracking: As we find a valid path to endWord, we backtrack to build all possible sequences.

2. C++ Code

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;

vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string>& wordList) {
    vector<vector<string>> result;
    if (wordList.find(endWord) == wordList.end()) return result;

    unordered_map<string, vector<vector<string>>> level;  // to store the paths at each level
    unordered_set<string> currentLevel, nextLevel;
    currentLevel.insert(beginWord);
    wordList.insert(endWord);
    bool found = false;

    while (!currentLevel.empty() && !found) {
        for (auto& word : currentLevel) wordList.erase(word);  // Remove words at this level
        nextLevel.clear();

        for (auto& word : currentLevel) {
            string temp = word;
            for (int i = 0; i < word.length(); i++) {
                char original = temp[i];
                temp[i] = '*';  // Replace character with *
                for (auto& neighbor : wordList) {
                    if (neighbor == temp) {
                        if (neighbor == endWord) found = true;
                        for (auto& path : level[word]) {
                            level[neighbor].push_back(path);
                        }
                        nextLevel.insert(neighbor);
                    }
                }
                temp[i] = original;
            }
        }

        currentLevel.swap(nextLevel);
    }

    for (auto& path : level[endWord]) {
        result.push_back(path);
    }

    return result;
}

int main() {
    string beginWord = "hit", endWord = "cog";
    unordered_set<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
    vector<vector<string>> result = findLadders(beginWord, endWord, wordList);
    
    for (const auto& path : result) {
        for (const auto& word : path) {
            cout << word << " ";
        }
        cout << endl;
    }

    return 0;
}

Explanation of C++ Code:

  1. unordered_set: We use unordered_set to store the words for quick lookup and removal.
  2. level map: This map stores the transformation sequences at each level.
  3. BFS: BFS is used to explore all possible transformations from beginWord to endWord.
  4. Backtracking: Once the BFS completes, we backtrack through the paths to generate all valid transformations.

3. Java Code

import java.util.*;

public class WordLadderII {
    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        List<List<String>> result = new ArrayList<>();
        if (!wordList.contains(endWord)) return result;

        Map<String, List<List<String>>> level = new HashMap<>();
        Set<String> currentLevel = new HashSet<>();
        Set<String> nextLevel = new HashSet<>();
        currentLevel.add(beginWord);
        wordList.add(endWord);
        boolean found = false;

        while (!currentLevel.isEmpty() && !found) {
            for (String word : currentLevel) wordList.remove(word); // Remove words at this level
            nextLevel.clear();

            for (String word : currentLevel) {
                char[] temp = word.toCharArray();
                for (int i = 0; i < temp.length; i++) {
                    char original = temp[i];
                    temp[i] = '*';  // Replace character with *
                    String pattern = new String(temp);
                    if (wordList.contains(pattern)) {
                        if (pattern.equals(endWord)) found = true;
                        for (List<String> path : level.getOrDefault(word, new ArrayList<>())) {
                            List<String> newPath = new ArrayList<>(path);
                            newPath.add(pattern);
                            level.computeIfAbsent(pattern, k -> new ArrayList<>()).add(newPath);
                        }
                        nextLevel.add(pattern);
                    }
                    temp[i] = original; // Restore original character
                }
            }

            currentLevel = nextLevel;
        }

        return level.getOrDefault(endWord, new ArrayList<>());
    }

    public static void main(String[] args) {
        WordLadderII wl = new WordLadderII();
        Set<String> wordList = new HashSet<>(Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        List<List<String>> result = wl.findLadders("hit", "cog", wordList);
        for (List<String> path : result) {
            System.out.println(path);
        }
    }
}

Explanation of Java Code:

  1. Set for fast lookup: We use Set<String> for wordList to quickly check the presence of words.
  2. BFS and Backtracking: Similar to Python, we use BFS for exploration and backtracking to generate paths.
  3. Level Map: Maps each word to its transformation sequences.

C Code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
#include <limits.h>

#define MAX_WORDS 1000
#define WORD_LENGTH 10

typedef struct Node {
    char word[WORD_LENGTH];
    struct Node* next;
} Node;

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

void enqueue(Queue* queue, char* word) {
    Node* temp = (Node*)malloc(sizeof(Node));
    strcpy(temp->word, word);
    temp->next = NULL;
    if (queue->rear) {
        queue->rear->next = temp;
    } else {
        queue->front = temp;
    }
    queue->rear = temp;
}

char* dequeue(Queue* queue) {
    if (queue->front == NULL) return NULL;
    Node* temp = queue->front;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    char* word = temp->word;
    free(temp);
    return word;
}

bool isAdjacent(char* word1, char* word2) {
    int diff = 0;
    for (int i = 0; word1[i] != '\0'; i++) {
        if (word1[i] != word2[i]) {
            diff++;
        }
        if (diff > 1) return false;
    }
    return diff == 1;
}

void findLadders(char* beginWord, char* endWord, char* wordList[], int wordCount) {
    // BFS approach to find shortest paths
    Queue* queue = createQueue();
    enqueue(queue, beginWord);

    while (queue->front != NULL) {
        char* current = dequeue(queue);

        // If current word is endWord, stop and print the path
        if (strcmp(current, endWord) == 0) {
            printf("Found transformation sequence\n");
            return;
        }

        for (int i = 0; i < wordCount; i++) {
            if (isAdjacent(current, wordList[i])) {
                enqueue(queue, wordList[i]);
            }
        }
    }

    printf("No transformation found\n");
}

int main() {
    char* wordList[] = {"hot", "dot", "dog", "lot", "log", "cog"};
    int wordCount = 6;

    findLadders("hit", "cog", wordList, wordCount);

    return 0;
}

C# Code

using System;
using System.Collections.Generic;

class WordLadderII {
    public IList<IList<string>> FindLadders(string beginWord, string endWord, HashSet<string> wordList) {
        var result = new List<IList<string>>();
        if (!wordList.Contains(endWord)) return result;

        var level = new Dictionary<string, List<List<string>>>();
        var currentLevel = new HashSet<string> { beginWord };
        var nextLevel = new HashSet<string>();
        wordList.Add(endWord);
        bool found = false;

        while (currentLevel.Count > 0 && !found) {
            foreach (var word in currentLevel) wordList.Remove(word); // Remove words at this level
            nextLevel.Clear();

            foreach (var word in currentLevel) {
                char[] temp = word.ToCharArray();
                for (int i = 0; i < temp.Length; i++) {
                    char original = temp[i];
                    temp[i] = '*';
                    string pattern = new string(temp);
                    if (wordList.Contains(pattern)) {
                        if (pattern == endWord) found = true;
                        foreach (var path in level.GetValueOrDefault(word, new List<List<string>>())) {
                            var newPath = new List<string>(path) { pattern };
                            level.GetValueOrDefault(pattern, new List<List<string>>()).Add(newPath);
                        }
                        nextLevel.Add(pattern);
                    }
                    temp[i] = original; // Restore original character
                }
            }

            currentLevel = new HashSet<string>(nextLevel);
        }

        foreach (var path in level.GetValueOrDefault(endWord, new List<List<string>>())) {
            result.Add(path);
        }

        return result;
    }

    public static void Main() {
        var wl = new WordLadderII();
        var wordList = new HashSet<string> { "hot", "dot", "dog", "lot", "log", "cog" };
        var result = wl.FindLadders("hit", "cog", wordList);
        foreach (var path in result) {
            Console.WriteLine(string.Join(" ", path));
        }
    }
}

JavaScript Code

function findLadders(beginWord, endWord, wordList) {
    let result = [];
    if (!wordList.has(endWord)) return result;

    let level = {};
    let currentLevel = new Set([beginWord]);
    let nextLevel = new Set();
    wordList.add(endWord);
    let found = false;

    while (currentLevel.size > 0 && !found) {
        for (let word of currentLevel) wordList.delete(word); // Remove words at this level
        nextLevel.clear();

        for (let word of currentLevel) {
            let temp = word.split('');
            for (let i = 0; i < temp.length; i++) {
                let original = temp[i];
                temp[i] = '*';
                let pattern = temp.join('');
                if (wordList.has(pattern)) {
                    if (pattern === endWord) found = true;
                    for (let path of (level[word] || [])) {
                        let newPath = [...path, pattern];
                        if (!level[pattern]) level[pattern] = [];
                        level[pattern].push(newPath);
                    }
                    nextLevel.add(pattern);
                }
                temp[i] = original; // Restore original character
            }
        }

        currentLevel = new Set(nextLevel);
    }

    return level[endWord] || [];
}

// Example test case
const beginWord = "hit";
const endWord = "cog";
const wordList = new Set(["hot", "dot", "dog", "lot", "log", "cog"]);
const result = findLadders(beginWord, endWord, wordList);
result.forEach(path => console.log(path.join(' ')));

Summary:

  • Approach: Use BFS to explore all possible words and keep track of the paths. Once the BFS completes, use backtracking to collect all possible shortest paths.
  • Time Complexity: O(N×M×26)O(N \times M \times 26)O(N×M×26), where N is the number of words and M is the length of each word.
  • Space Complexity: O(N×M)O(N \times M)O(N×M), due to the storage for the BFS queue and paths.