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 the shortest path graph, where each node represents a word, and edges exist between words that differ by one character.
2. During BFS, calculate the distance of each word from the start word and track neighbors for each word.
3. Use DFS to backtrack from the end word to the start word, exploring all shortest paths and recording valid sequences.

Complexity:

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

Java Implementation:

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

        dict.add(start); // Add the start word to the dictionary

        // Perform BFS to build the graph and calculate distances
        bfs(start, end, dict, nodeNeighbors, distance);

        // Perform DFS to backtrack and find all shortest paths
        dfs(start, end, dict, nodeNeighbors, distance, solution, res);

        return res;
    }

    private void bfs(String start, String end, Set dict, Map> nodeNeighbors, Map distance) {
        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 (!distance.containsKey(neighbor)) {
                        distance.put(neighbor, curDistance + 1);
                        if (neighbor.equals(end)) {
                            foundEnd = true;
                        } else {
                            queue.offer(neighbor);
                        }
                    }
                    // Add neighbors only if they are part of the shortest path
                    if (distance.get(neighbor) == curDistance + 1) {
                        nodeNeighbors.get(cur).add(neighbor);
                    }
                }
            }
            if (foundEnd) break;
        }
    }

    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;
        }
        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));
        } else {
            for (String next : nodeNeighbors.get(cur)) {
                dfs(next, end, dict, nodeNeighbors, distance, solution, res);
            }
        }

        solution.remove(solution.size() - 1);
    }
}