Vultr DocsLatest Content

Word Ladder II

Updated on 27 June, 2025
Word Ladder II header image

Problem Statement

The problem involves generating all possible shortest transformation sequences that transform a given beginWord into an endWord using a specified wordList. A transformation sequence is valid if each consecutive word in the sequence differs by only one letter and all intermediate words exist in wordList. The beginWord itself does not need to be in the wordList, but the sequence must terminate at the endWord. If no sequence meets these requirements, the function should return an empty list. Each valid sequence is represented by a list of words starting with beginWord and ending with endWord.

The transformation must adhere to the sequence rules, where every adjacent pair of words changes by exactly one letter, ensuring that the sequence moves logically from the beginWord to the endWord using allowable words in the wordList.

Examples

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, therefore there is no valid transformation sequence.

Constraints

  • 1 <= beginWord.length <= 5
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 500
  • 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 sum of all shortest transformation sequences does not exceed 105.

Approach and Intuition

  1. Construct a Graph:

    • Understand that the solution requires building a type of graph where each node represents a word and edges connect words that differ by exactly one letter.
    • This implies a necessity to efficiently check which words can transition into others, which can be optimized using a pre-processing step that transforms each word into various possible single-letter mutations.

  2. Breadth-First Search (BFS):

    • Utilize BFS for finding the shortest path in unweighted graphs – here, our graph's nodes are the words, and edges represent a valid one-letter transformation.
    • Begin BFS from beginWord and proceed to explore all its neighbors (words differing by one letter), marking each word visited by storing them in a queue, till endWord is reached.
    • As BFS explores layers by layers, it guarantees that we first reach endWord by the shortest path.

  3. Backtracking for Multiple Shortest Paths:

    • It's crucial not just to find a shortest path, but all paths with the minimal number of transformations.
    • Once endWord is reached during the BFS phase, perform a backtracking step to unearth all potential paths that lead to endWord within the same minimal transformation steps.

  4. Handling Edge Cases:

    • If endWord isn't in wordList, a solution is impossible, so function should return an empty list immediately.
    • Utilize a hash set for wordList to allow O(1) complexity checks if a word can be part of the sequence.

Examples Analysis:

  • For Example 1:

    • "hit" begins the sequence, and two paths provide minimal transformations to "cog" using the available words. Both transformations found ("hit" -> "hot" -> "dot" -> "dog" -> "cog" and "hit" -> "hot" -> "lot" -> "log" -> "cog") meet the criteria of differing by only one letter between consecutive words and being the shortest possible such sequences.

  • For Example 2:

    • As "cog" is not present in the wordList, there is no valid sequence possible, leading to a return of an empty array.

Solutions

  • C++
  • Java
  • JavaScript
  • Python
cpp 
class WordLadderSolver {
public:
    unordered_map<string, vector<string>> graph;
    vector<string> path;
    vector<vector<string>> allPaths;
    
    // Generate potential words by changing each character of the current word
    vector<string> getNeighbors(string &word, unordered_set<string> &dictionary) {
        vector<string> neighbors;
    
        for (int pos = 0; pos < word.length(); pos++) {
            char originalChar = word[pos];
    
            // Cycle through all possible characters from 'a' to 'z'
            for (char ch = 'a'; ch <= 'z'; ch++) {
                word[pos] = ch;
    
                // Check if new word is in the dictionary
                if (ch != originalChar && dictionary.count(word)) {
                    neighbors.push_back(word);
                }
            }
            word[pos] = originalChar; // reset the word to its original state
        }
        return neighbors;
    }
    
    // Use DFS to find all paths from end to start
    void findPaths(string &start, string &end) {
        if (start == end) {
            allPaths.push_back(vector<string>(path.rbegin(), path.rend()));
            return;
        }
    
        // Traverse each neighbor
        for (auto &neighbor : graph[start]) {
            path.push_back(neighbor);
            findPaths(neighbor, end);
            path.pop_back();
        }
    }
    
    // Construct a graph using BFS starting from the beginWord
    void buildGraph(string &beginWord, string &endWord, unordered_set<string> &dict) {
        queue<string> queue;
        queue.push(beginWord);
        unordered_map<string, int> visited;
        visited[beginWord] = 1;
    
        while (!queue.empty()) {
            vector<string> layerVisited;
            int layerSize = queue.size();
    
            while (layerSize--) {
                string currentWord = queue.front();
                queue.pop();
    
                vector<string> adjWords = getNeighbors(currentWord, dict);
                for (string &adjWord : adjWords) {
                    layerVisited.push_back(adjWord);
                    graph[adjWord].push_back(currentWord);
    
                    if (visited.find(adjWord) == visited.end()) {
                        queue.push(adjWord);
                        visited[adjWord] = 1;
                    }
                }
            }
    
            // Remove visited words from the dictionary
            for (string &word : layerVisited) {
                dict.erase(word);
            }
        }
    }
    
    vector<vector<string>> findWordLadders(string beginWord, string endWord, vector<string> &wordList) {
        unordered_set<string> setOfWords(wordList.begin(), wordList.end());
    
        // Build graph from the end word to the beginning word
        buildGraph(beginWord, endWord, setOfWords);
    
        // Initialize path with endWord and search for all paths from the end
        path.push_back(endWord);
        findPaths(endWord, beginWord);
    
        return allPaths;
    }
};

The C++ class WordLadderSolver implements algorithms to find all shortest transformation sequences from a beginWord to an endWord, utilizing a list of words as a dictionary. This solution employs BFS and DFS to ensure all potential transformations are considered, optimizing the process to find minimal transformation paths.

  • The getNeighbors function generates potential words by changing each letter of the current word to every letter from 'a' to 'z', verifying if the new word exists in the dictionary.
  • The findPaths function employs a depth-first search (DFS) to traverse through each possible path from the end word to the start, adding valid paths to the allPaths vector.
  • buildGraph uses a breadth-first search (BFS) from the beginWord, constructing a graph where each word points to all valid subsequent transformations found in the dictionary.
  • The findWordLadders function integrates all functionalities: it prepares the dictionary, invokes graph construction using the beginWord and endWord, and triggers the DFS-based path finding.

The process:

  1. Convert the word list into an unordered set (setOfWords) to allow for efficient access and mutation operations.
  2. Construct a graph linking words by feasible one-letter transformations using buildGraph.
  3. Start DFS path finding with the endWord using findPaths to collect all possible shortest paths found in allPaths.

The code structure includes essential data management for graph traversal and backtracking, ensuring that the implementation efficiently finds all minimum-length word ladders while handling edge cases like when no path exists.

java 
class Solution {
    Map<String, List<String>> graph = new HashMap<>();
    List<String> path = new ArrayList<>();
    List<List<String>> allPaths = new ArrayList<>();
    
    private List<String> getAdjacent(String node, Set<String> dictionary) {
        List<String> adjNodes = new ArrayList<>();
        char[] chars = node.toCharArray();
    
        for (int index = 0; index < node.length(); index++) {
            char originalChar = chars[index];
            for (char c = 'a'; c <= 'z'; c++) {
                chars[index] = c;
                String newWord = String.valueOf(chars);
                if (c != originalChar && dictionary.contains(newWord)) {
                    adjNodes.add(newWord);
                }
            }
            chars[index] = originalChar;
        }
        return adjNodes;
    }
    
    private void searchPath(String start, String end) {
        if (start.equals(end)) {
            List<String> temp = new ArrayList<>(path);
            Collections.reverse(temp);
            allPaths.add(temp);
        }
    
        if (!graph.containsKey(start)) {
            return;
        }
    
        for (String next : graph.get(start)) {
            path.add(next);
            searchPath(next, end);
            path.remove(path.size() - 1);
        }
    }
    
    private void traverse(String startWord, String endWord, Set<String> dictionary) {
        Queue<String> queue = new LinkedList<>();
        queue.add(startWord);
        Map<String, Boolean> visited = new HashMap<>();
        visited.put(startWord, true);
    
        while (!queue.isEmpty()) {
            String current = queue.poll();
            List<String> neighbors = getAdjacent(current, dictionary);
            for (String neighbor : neighbors) {
                if (!graph.containsKey(neighbor)) {
                    graph.put(neighbor, new ArrayList<>());
                }
                graph.get(neighbor).add(current);
                if (!visited.containsKey(neighbor)) {
                    queue.add(neighbor);
                    visited.put(neighbor, true);
                }
            }
            dictionary.removeAll(neighbors);
        }
    }
    
    public List<List<String>> findLadders(
        String beginWord,
        String endWord,
        List<String> wordList
    ) {
        Set<String> copyList = new HashSet<>(wordList);
        traverse(beginWord, endWord, copyList);
        path.add(endWord);
        searchPath(endWord, beginWord);
    
        return allPaths;
    }
}

The provided Java solution resolves the "Word Ladder II" problem by finding all the possible shortest transformation sequences from a start word to an end word. Each transformation in the sequence changes only one letter at a time, with all intermediate words existing in a given dictionary. Here's a breakdown of the solution methodology:

  • Graph Construction: The solution first constructs a graph using a breadth-first search approach. It begins from the start word and explores all possible one-letter transformations that exist in the dictionary, building a mapping of each word to its possible predecessors.

  • Backtracking for Path Finding: Once the graph is constructed, the algorithm then performs a depth-first search to find all paths from the end word to the start word using backtracking. This ensures that all potential transformations leading back to the start word are explored.

  • Data Structures Employed:

    • HashMap and HashSet for storing words and their relationships efficiently.
    • Queue for BFS implementation to traverse the dictionary.
    • ArrayList for capturing paths and final results.

  • Algorithm Flow:

    1. Initialize the adjacency list graph, path list, and allPaths list.
    2. Define getAdjacent function to retrieve all adjacent nodes (words differing by one letter) for a given node or word from the dictionary.
    3. Implement searchPath using DFS to find and record all paths from end word to start word.
    4. Use traverse function with BFS to populate the graph with each node and its corresponding adjacent nodes.
    5. findLadders function serves as the main function to initiate the graph traversal and path searches, returning the list of all shortest transformation paths.

By following this approach, the solution identifies all the shortest paths efficiently, ensuring that each transformation is valid and minimal. The use of BFS for initial graph construction and DFS for path search balances between constructing accurate node relations and ensuring comprehensive path exploration.

js 
var computeLadders = function (startWord, targetWord, wordsList) {
    let adjacencyList = {};
    let currentPath = [];
    let pathsResult = [];
    
    function locateNeighbors(currentWord, wordsSet) {
        let potential = [];
        let lettersArray = Array.from(currentWord);
        for (let index = 0; index < lettersArray.length; index++) {
            let originalCharacter = lettersArray[index];
            for (let code = "a".charCodeAt(0); code <= "z".charCodeAt(0); code++) {
                lettersArray[index] = String.fromCharCode(code);
                let formedWord = lettersArray.join("");
                if (code === originalCharacter.charCodeAt(0) || !wordsSet.has(formedWord)) {
                    continue;
                }
                potential.push(formedWord);
            }
            lettersArray[index] = originalCharacter;
        }
        return potential;
    }
    
    function findPath(source, dest) {
        if (source === dest) {
            let pathCopy = Array.from(currentPath);
            pathCopy.reverse();
            pathsResult.push(pathCopy);
        }
    
        if (!adjacencyList[source]) {
            return;
        }
    
        adjacencyList[source].forEach((adjacent) => {
            currentPath.push(adjacent);
            findPath(adjacent, dest);
            currentPath.pop();
        });
    }
    
    function breadthFirstSearch(startWord, targetWord, wordsSet) {
        let queue = [startWord];
        wordsSet.delete(startWord);
        let enqueuedWords = { [startWord]: true };
        while (queue.length > 0) {
            let layer = [];
            for (let i = queue.length - 1; i >= 0; i--) {
                let word = queue.shift();
                let adjacentWords = locateNeighbors(word, wordsSet);
                adjacentWords.forEach((neighb) => {
                    layer.push(neighb);
                    if (!adjacencyList.hasOwnProperty(neighb)) {
                        adjacencyList[neighb] = [];
                    }
                    adjacencyList[neighb].push(word);
                    if (!enqueuedWords[neighb]) {
                        queue.push(neighb);
                        enqueuedWords[neighb] = true;
                    }
                });
            }
            layer.forEach((word) => wordsSet.delete(word));
        }
    }
    
    let wordsSet = new Set(wordsList);
    breadthFirstSearch(startWord, targetWord, wordsSet);
    
    currentPath = [targetWord];
    findPath(targetWord, startWord);
    
    return pathsResult;
};

The given JavaScript code outlines a solution for generating all shortest transformation sequences from a given startWord to a targetWord using a set of intermediate words provided in wordsList. The solution primarily utilizes a breadth-first search (BFS) approach combined with backtracking to record and trace each valid transformation path.

Summarized Steps in the Code:

  1. Initialize adjacencyList to map each word to its adjacent transformable words, currentPath to track the path being explored, and pathsResult to store all shortest paths.
  2. Define locateNeighbors function to find all possible single-step transformations of a word within the given word set by changing one character at a time through the entire alphabet.
  3. Utilize breadthFirstSearch function to:
    • Build adjacencyList by exploring each word level by level.
    • Use a queue for BFS traversal and a set (wordsSet) to keep track of words already in the queue or explored.
    • For each word, locate neighbors, add them to the dequeue list, and update the adjacency list to reflect the connection from neighbor back to the current word.
  4. After constructing the adjacency list via BFS, implement findPath function to:
    • Use backtracking to find all paths from the targetWord to startWord by following backward links created during BFS.
    • Each path found is reversed to transform from startWord to targetWord and added to pathsResult.
  5. Begin the search with breadthFirstSearch and follow it by tracing paths using findPath.

Results Processing:

  • The final outputs, stored in pathsResult, consist of all shortest possible transformations from startWord to targetWord that can be accomplished in the fewest number of transformations with the given word list.

The method effectively finds all shortest transformation sequences, ensuring computational efficiency by utilizing BFS to limit the search space and backtracking to enumerate possible solutions based on the BFS results.

python 
class GraphPathFinder:
    def __init__(self):
        self.adjacencyList: Dict[str, List[str]] = {}
        self.activePath: List[str] = []
        self.allPaths: List[List[str]] = []
    
    def locateNeighbors(self, node: str, words: Set[str]) -> List[str]:
        neighbors: List[str] = []
        nodeChars = list(node)
        for idx in range(len(nodeChars)):
            originalChar = nodeChars[idx]
            for char in "abcdefghijklmnopqrstuvwxyz":
                nodeChars[idx] = char
                possibleWord = "".join(nodeChars)
                if char == originalChar or possibleWord not in words:
                    continue
                neighbors.append(possibleWord)
            nodeChars[idx] = originalChar
        return neighbors
    
    def pathSearch(self, start: str, end: str):
        if start == end:
            pathSnapshot = self.activePath.copy()
            pathSnapshot.reverse()
            self.allPaths.append(pathSnapshot)
    
        if start not in self.adjacencyList:
            return
    
        for adjacent in self.adjacencyList[start]:
            self.activePath.append(adjacent)
            self.pathSearch(adjacent, end)
            self.activePath.pop()
    
    def layerByLayerSearch(self, firstWord: str, lastWord: str, words: Set[str]):
        queue: Deque[str] = deque([firstWord])
        words.discard(firstWord)
        enqueued: Dict[str, bool] = {firstWord: True}
        while queue:
            currentLayer: List[str] = []
            for _ in range(len(queue)):
                currentWord = queue.popleft()
                neighboringWords = self.locateNeighbors(currentWord, words)
                for neighbor in neighboringWords:
                    currentLayer.append(neighbor)
                    if neighbor not in self.adjacencyList:
                        self.adjacencyList[neighbor] = []
                    self.adjacencyList[neighbor].append(currentWord)
                    if neighbor not in enqueued:
                        queue.append(neighbor)
                        enqueued[neighbor] = True
            for word in currentLayer:
                words.discard(word)
    
    def findRoutes(
        self, startWord: str, endWord: str, listOfWords: List[str]
    ) -> List[List[str]]:
        setOfWords: Set[str] = set(listOfWords)
        self.layerByLayerSearch(startWord, endWord, setOfWords)
    
        self.activePath = [endWord]
        self.pathSearch(endWord, startWord)
    
        return self.allPaths

The provided Python3 code is designed to solve the problem of finding all possible paths (sequences of words) from a starting word to a target word, where each consecutive word in the sequence can only differ by one letter. This challenge is tackled through a class named GraphPathFinder that contains methods to search the paths in a graph-like structure. Here's how the solution is structured:

  • The class GraphPathFinder initializes three main attributes:

    • adjacencyList to maintain a dictionary mapping each word to its adjacent words.
    • activePath to track the current path being explored.
    • allPaths to store all possible paths from the target to the start word.

  • locateNeighbors function:

    • Takes a node (word) and a set of all possible words.
    • Finds all neighboring words that differ by exactly one character.
    • Returns a list of these neighboring words.

  • pathSearch function:

    • Recursively explores each path from the start word to the end word using backtracking.
    • If a path reaches the end word, it adds a copy (in reverse) to allPaths.

  • layerByLayerSearch function:

    • Performs a breadth-first search (BFS) to explore the words layer by layer starting from the first word.
    • Builds the adjacencyList for each word during the traversal.
    • Discards words from the original set once they are enqueued to prevent reprocessing.

  • findRoutes method:

    • Converts the list of words into a set for efficient lookup.
    • Calls layerByLayerSearch to populate adjacencyList.
    • Initializes the activePath with the end word and calls pathSearch to find all paths by recursively exploring reachable words.
    • Returns the list of all paths from the starting word to the ending word, where paths are lists of words.

This implementation allows for efficient path finding in word ladder problems by utilizing graph traversal techniques such as BFS for building connectivity and depth-first search (DFS) for path finding, combined with backtracking to explore all possible paths.

Comments

No comments yet.