Word Ladder II

DFS Backtracking — Exploring All Transformation Paths — Watch the DFS explore every possible path through the word transformation graph, backtracking when hitting dead ends or exceeding the minimum path length.

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return {};

        vector<vector<string>> result;
        int minLen = INT_MAX;

        function<void(const string&, vector<string>&, unordered_set<string>&)> dfs;
        dfs = [&](const string& word, vector<string>& path, unordered_set<string>& visited) {
            if ((int)path.size() > minLen) return;
            if (word == endWord) {
                if ((int)path.size() < minLen) {
                    minLen = path.size();
                    result.clear();
                }
                if ((int)path.size() == minLen) {
                    result.push_back(path);
                }
                return;
            }
            string temp = word;
            for (int i = 0; i < (int)temp.size(); i++) {
                char orig = temp[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == orig) continue;
                    temp[i] = c;
                    if (wordSet.count(temp) && !visited.count(temp)) {
                        visited.insert(temp);
                        path.push_back(temp);
                        dfs(temp, path, visited);
                        path.pop_back();
                        visited.erase(temp);
                    }
                }
                temp[i] = orig;
            }
        };

        unordered_set<string> visited = {beginWord};
        vector<string> path = {beginWord};
        dfs(beginWord, path, visited);
        return result;
    }
};

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
        word_set = set(wordList)
        if endWord not in word_set:
            return []

        result = []
        min_len = float('inf')

        def dfs(word, path, visited):
            nonlocal min_len
            if len(path) > min_len:
                return
            if word == endWord:
                if len(path) < min_len:
                    min_len = len(path)
                    result.clear()
                if len(path) == min_len:
                    result.append(list(path))
                return
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    if c == word[i]:
                        continue
                    new_word = word[:i] + c + word[i+1:]
                    if new_word in word_set and new_word not in visited:
                        visited.add(new_word)
                        path.append(new_word)
                        dfs(new_word, path, visited)
                        path.pop()
                        visited.remove(new_word)

        dfs(beginWord, [beginWord], {beginWord})
        return result

class Solution {
    List<List<String>> result = new ArrayList<>();
    int minLen = Integer.MAX_VALUE;

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

        List<String> path = new ArrayList<>();
        path.add(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        dfs(beginWord, endWord, wordSet, path, visited);
        return result;
    }

    private void dfs(String word, String endWord, Set<String> wordSet,
                     List<String> path, Set<String> visited) {
        if (path.size() > minLen) return;
        if (word.equals(endWord)) {
            if (path.size() < minLen) {
                minLen = path.size();
                result.clear();
            }
            if (path.size() == minLen) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char orig = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == orig) continue;
                chars[i] = c;
                String newWord = new String(chars);
                if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                    visited.add(newWord);
                    path.add(newWord);
                    dfs(newWord, endWord, wordSet, path, visited);
                    path.remove(path.size() - 1);
                    visited.remove(newWord);
                }
            }
            chars[i] = orig;
        }
    }
}

BFS with Path Storage — Level-by-Level Exploration — BFS explores all words at the same distance before moving deeper. Each complete path is stored in the queue, guaranteeing we find all shortest paths.

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return {};

        vector<vector<string>> result;
        queue<vector<string>> q;
        q.push({beginWord});
        unordered_set<string> visited = {beginWord};
        bool found = false;

        while (!q.empty() && !found) {
            int levelSize = q.size();
            unordered_set<string> levelVisited;

            for (int i = 0; i < levelSize; i++) {
                vector<string> path = q.front();
                q.pop();
                string word = path.back();
                string temp = word;

                for (int j = 0; j < (int)temp.size(); j++) {
                    char orig = temp[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        temp[j] = c;
                        if (temp == endWord) {
                            vector<string> newPath = path;
                            newPath.push_back(temp);
                            result.push_back(newPath);
                            found = true;
                        } else if (wordSet.count(temp) && !visited.count(temp)) {
                            vector<string> newPath = path;
                            newPath.push_back(temp);
                            q.push(newPath);
                            levelVisited.insert(temp);
                        }
                    }
                    temp[j] = orig;
                }
            }
            for (const string& w : levelVisited) visited.insert(w);
        }
        return result;
    }
};

from collections import deque

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
        word_set = set(wordList)
        if endWord not in word_set:
            return []

        result = []
        queue = deque([[beginWord]])
        visited = {beginWord}
        found = False

        while queue and not found:
            level_size = len(queue)
            level_visited = set()

            for _ in range(level_size):
                path = queue.popleft()
                word = path[-1]

                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c == word[i]:
                            continue
                        new_word = word[:i] + c + word[i+1:]
                        if new_word == endWord:
                            result.append(path + [new_word])
                            found = True
                        elif new_word in word_set and new_word not in visited:
                            queue.append(path + [new_word])
                            level_visited.add(new_word)

            visited |= level_visited

        return result

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

        Queue<List<String>> queue = new LinkedList<>();
        queue.add(new ArrayList<>(Arrays.asList(beginWord)));
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        boolean found = false;

        while (!queue.isEmpty() && !found) {
            int levelSize = queue.size();
            Set<String> levelVisited = new HashSet<>();

            for (int i = 0; i < levelSize; i++) {
                List<String> path = queue.poll();
                String word = path.get(path.size() - 1);
                char[] chars = word.toCharArray();

                for (int j = 0; j < chars.length; j++) {
                    char orig = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (newWord.equals(endWord)) {
                            List<String> newPath = new ArrayList<>(path);
                            newPath.add(newWord);
                            result.add(newPath);
                            found = true;
                        } else if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                            List<String> newPath = new ArrayList<>(path);
                            newPath.add(newWord);
                            queue.add(newPath);
                            levelVisited.add(newWord);
                        }
                    }
                    chars[j] = orig;
                }
            }
            visited.addAll(levelVisited);
        }
        return result;
    }
}

BFS Predecessor Map + DFS Path Reconstruction — Phase 1: BFS builds a lightweight predecessor map storing only which words lead to which. Phase 2: DFS backtracks from endWord through predecessors to reconstruct all shortest paths.

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return {};

        // Phase 1: BFS to build predecessor map
        unordered_map<string, unordered_set<string>> predecessors;
        unordered_set<string> currentLevel = {beginWord};
        unordered_set<string> visited = {beginWord};
        bool found = false;

        while (!currentLevel.empty() && !found) {
            // Mark current level as visited before processing
            for (const string& w : currentLevel) visited.insert(w);
            unordered_set<string> nextLevel;

            for (const string& word : currentLevel) {
                string temp = word;
                for (int i = 0; i < (int)temp.size(); i++) {
                    char orig = temp[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        temp[i] = c;
                        if (temp == endWord) {
                            predecessors[temp].insert(word);
                            found = true;
                        } else if (wordSet.count(temp) && !visited.count(temp)) {
                            nextLevel.insert(temp);
                            predecessors[temp].insert(word);
                        }
                    }
                    temp[i] = orig;
                }
            }
            currentLevel = nextLevel;
        }

        if (!found) return {};

        // Phase 2: DFS backtracking from endWord
        vector<vector<string>> result;
        vector<string> path = {endWord};

        function<void(const string&)> dfs = [&](const string& word) {
            if (word == beginWord) {
                result.push_back(vector<string>(path.rbegin(), path.rend()));
                return;
            }
            for (const string& pred : predecessors[word]) {
                path.push_back(pred);
                dfs(pred);
                path.pop_back();
            }
        };

        dfs(endWord);
        return result;
    }
};

from collections import defaultdict

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
        word_set = set(wordList)
        if endWord not in word_set:
            return []

        # Phase 1: BFS to build predecessor map
        predecessors = defaultdict(set)
        current_level = {beginWord}
        visited = {beginWord}
        found = False

        while current_level and not found:
            visited |= current_level
            next_level = set()

            for word in current_level:
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c == word[i]:
                            continue
                        new_word = word[:i] + c + word[i+1:]
                        if new_word == endWord:
                            predecessors[new_word].add(word)
                            found = True
                        elif new_word in word_set and new_word not in visited:
                            next_level.add(new_word)
                            predecessors[new_word].add(word)

            current_level = next_level

        if not found:
            return []

        # Phase 2: DFS backtracking from endWord
        result = []

        def dfs(word, path):
            if word == beginWord:
                result.append(path[::-1])
                return
            for pred in predecessors[word]:
                path.append(pred)
                dfs(pred, path)
                path.pop()

        dfs(endWord, [endWord])
        return result

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

        // Phase 1: BFS to build predecessor map
        Map<String, Set<String>> predecessors = new HashMap<>();
        Set<String> currentLevel = new HashSet<>();
        currentLevel.add(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        boolean found = false;

        while (!currentLevel.isEmpty() && !found) {
            visited.addAll(currentLevel);
            Set<String> nextLevel = new HashSet<>();

            for (String word : currentLevel) {
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char orig = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        chars[i] = c;
                        String newWord = new String(chars);
                        if (newWord.equals(endWord)) {
                            predecessors.computeIfAbsent(newWord, k -> new HashSet<>()).add(word);
                            found = true;
                        } else if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                            nextLevel.add(newWord);
                            predecessors.computeIfAbsent(newWord, k -> new HashSet<>()).add(word);
                        }
                    }
                    chars[i] = orig;
                }
            }
            currentLevel = nextLevel;
        }

        if (!found) return result;

        // Phase 2: DFS backtracking from endWord
        List<String> path = new ArrayList<>();
        path.add(endWord);
        buildPaths(endWord, beginWord, predecessors, path, result);
        return result;
    }

    private void buildPaths(String word, String beginWord,
                            Map<String, Set<String>> predecessors,
                            List<String> path, List<List<String>> result) {
        if (word.equals(beginWord)) {
            List<String> reversed = new ArrayList<>(path);
            Collections.reverse(reversed);
            result.add(reversed);
            return;
        }
        if (!predecessors.containsKey(word)) return;
        for (String pred : predecessors.get(word)) {
            path.add(pred);
            buildPaths(pred, beginWord, predecessors, path, result);
            path.remove(path.size() - 1);
        }
    }
}