126. Word Ladder II

Problem Link

Description

---

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

 

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.

Solution

---

C++

class Solution {
public:
    vector<vector<string>> findLadders(string s, string t, vector<string>& A) {
        
        set<string> st;
        for(auto a: A)
            st.insert(a);
        if(!st.count(t))
            return {};
            
        queue<pair<string, int>> q;
        q.push({s, 0});
        
        map<string, int> dp;
        dp[s] = 0;
        
        map<string, vector<string>> prv;
        
        while(!q.empty()) {
            auto [u, dpu] = q.front(); q.pop();
            
            if(dpu > dp[u])
                continue;
            
            int m = u.size();
            for(int i=0; i<m; i++) {
                char c = u[i];
                for(char d='a'; d<='z'; d++) {
                    if(c == d)
                        continue;
                    string v = u;
                    v[i] = d;
                    
                    if(!st.count(v))
                        continue;
                    if(!dp.count(v) || dpu + 1 < dp[v]) {
                        int dpv = dpu + 1;
                        q.push({v, dpv});
                        dp[v] = dpv;
                        
                        prv[v] = {u};
                    } else if(dpu + 1 == dp[v])
                        prv[v].push_back(u);
                }
            }
        }
        
        vector<vector<string>> ans;
        function<void (string, vector<string>&)> dfs=[&](string u, vector<string>&cur) {
            if(u == s) {
                reverse(cur.begin(), cur.end());
                ans.push_back(cur);
                reverse(cur.begin(), cur.end());
                return;
            }
            
            for(auto v: prv[u]) {
                cur.push_back(v);
                dfs(v, cur);
                cur.pop_back();
            }
        };
        vector<string> cur = {t};
        dfs(t, cur);
        
        return ans;
    }
};

Python3

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        res = []
        s = set(wordList)
        mmin = float('inf')
        queue = collections.deque([[beginWord]])
        level = 1
        visited = set()
 
        while queue:
            ladder = queue.popleft()
            n = len(ladder)
            
            if n > level:
                for v in visited:
                    s.remove(v)
                visited.clear()
                
                if n <= mmin:
                    level = n
                else:
                    break
                    
            word = ladder[-1]
            for i in range(len(word)):
                for w in string.ascii_lowercase:
                    newWord = word[:i] + w + word[i + 1:]
                    if newWord in s:
                        visited.add(newWord)
                        if newWord == endWord:
                            minLevel = n + 1
                            res.append(ladder + [newWord])
                        else:
                            queue.append((ladder + [newWord]))
                
        return res