Word Ladder II

122.Word Ladder II

Graph

Breadth-First Search

Depth-First Search

Problem Statement:

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

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

Return all shortest transformation sequences in a list of lists. If no such transformation sequence exists, return an empty list.

Algorithm:

1. Use BFS to build a graph where each word points to its valid neighbors (words that differ by one character).
2. Record the distance of each word from the starting word during BFS.
3. Use DFS to backtrack from the end word to the start word, generating all shortest paths.

Complexity:

Time: O(N × L² + V + E), where N is the number of words, L is the word length, V is the number of words in the graph, and E is the number of edges. | Space: O(V + E).

Java Implementation:

public class Solution {
    public List> findLadders(String start, String end, List wordList) {
        // Use a set for O(1) lookups
        Set dict = new HashSet<>(wordList);
        List> res = new ArrayList<>();
        Map> nodeNeighbors = new HashMap<>(); // Graph of word neighbors
        Map distance = new HashMap<>(); // Distance of each word from start
        List solution = new ArrayList<>();

        dict.add(start); // Include start word in the dictionary
        bfs(start, end, dict, nodeNeighbors, distance); // Perform BFS to build the graph
        dfs(start, end, dict, nodeNeighbors, distance, solution, res); // Perform DFS to find paths
        return res;
    }

    private void bfs(String start, String end, Set dict, Map> nodeNeighbors, Map distance) {
        // Initialize the neighbors map
        for (String word : dict)
            nodeNeighbors.put(word, new ArrayList<>());

        Queue queue = new LinkedList<>();
        queue.offer(start);
        distance.put(start, 0);

        while (!queue.isEmpty()) {
            int count = queue.size();
            boolean foundEnd = false;

            for (int i = 0; i < count; i++) {
                String cur = queue.poll();
                int curDistance = distance.get(cur);
                List neighbors = getNeighbors(cur, dict);

                for (String neighbor : neighbors) {
                    // If this neighbor hasn't been visited yet, calculate its distance
                    if (!distance.containsKey(neighbor)) {
                        distance.put(neighbor, curDistance + 1);
                        if (neighbor.equals(end)) foundEnd = true;
                        else queue.offer(neighbor); // Add to queue for further processing
                    }
                    // Add the neighbor to the current word's adjacency list if it's part of the shortest path
                    if (distance.get(neighbor) == curDistance + 1)
                        nodeNeighbors.get(cur).add(neighbor);
                }
            }
            if (foundEnd) break; // Stop if we find the end word
        }
    }

    private List getNeighbors(String node, Set dict) {
        List res = new ArrayList<>();
        char[] chars = node.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char oldChar = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == oldChar) continue;

                chars[i] = c;
                String newWord = String.valueOf(chars);
                if (dict.contains(newWord)) res.add(newWord);
            }
            chars[i] = oldChar; // Restore original character
        }
        return res;
    }

    private void dfs(String cur, String end, Set dict, Map> nodeNeighbors, Map distance, List solution, List> res) {
        solution.add(cur);
        if (cur.equals(end)) res.add(new ArrayList<>(solution)); // Found a valid path
        else
            for (String next : nodeNeighbors.get(cur))
                dfs(next, end, dict, nodeNeighbors, distance, solution, res); // Explore neighbors
        solution.remove(solution.size() - 1); // Backtrack to try other paths
    }
}