# 126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note:
  • Return an empty list if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same. 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: The endWord "cog" is not in wordList, therefore no possible transformation.

# Solution

Approach 1: First BFS to get the shortest path length, and then DFS to get all shortest paths.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

// First BFS to get the shortest path length, and then DFS to get all shortest paths.
class Solution {
private:
    unordered_map<string,vector<string>> umap;
    vector<vector<string>> res;
    bool isTransformable(string a, string b) {
        if (a.size() != b.size())
            return false;
        int count = 0;
        for (int i = 0; i < a.size(); ++i)
        {
            if (a[i] != b[i])
                count++;
            if (count > 1)
                break;
        }
        return count == 1;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        bool visited[wordList.size()] = {false};
        queue<string> q;
        q.push(beginWord);
        int level = 1;
        bool found = false;
        while (!q.empty() && !found)
        {
            level++;
            int qSize = q.size();
            unordered_set<int> buf;
            for (int i = 0; i < qSize; ++i)
            {
                string curr = q.front();
                q.pop();
                for (int j = 0; j < wordList.size(); ++j)
                {
                    if (!visited[j] && isTransformable(curr, wordList[j]))
                    {
                        if (!found && wordList[j] == endWord)
                            found = true;
                        buf.insert(j);
                        umap[curr].push_back(wordList[j]);
                    }
                }
            }
            for (unordered_set<int>::iterator it = buf.begin(); it != buf.end(); ++it)
            {
                visited[*it] = true;
                q.push(wordList[*it]);
            }
        }
        return (found) ? level : 0;
    }
    void doFindLadders(string beginWord, string endWord, vector<string>& wordList, vector<string>& buf, int level) {
        buf.push_back(beginWord);
        if (beginWord == endWord)
        {
            res.push_back(buf);
            buf.pop_back();
            return;
        }
        if (level > 1)
        {
            for (int i = 0; i < umap[beginWord].size(); ++i)
            {
                doFindLadders(umap[beginWord][i], endWord, wordList, buf, level-1);
            }
        }
        buf.pop_back();
    }
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        // Remove beginWord from wordList to avoid the infinit loop.
        for (int i = 0; i < wordList.size(); ++i)
        {
            if (wordList[i] == beginWord)
            {
                wordList.erase(wordList.begin() + i);
                break;
            }
        }
        int len = ladderLength(beginWord, endWord, wordList);
        vector<string> buf;
        doFindLadders(beginWord, endWord, wordList, buf, len);
        return res;
    }
};