LeetCode [126] Word Ladder II

 126. Word Ladder II

Hard

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

class Solution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> dict(wordList.begin(), wordList.end()); vector<vector<string>> ret; queue<vector<string>> que; int n = beginWord.size(), minLen = INT_MAX, curLevel = 1; que.push(vector<string>(1, beginWord)); dict.erase(beginWord); unordered_set<string> usedWords; while(!que.empty()){ vector<string> vec = que.front(); que.pop(); string s = vec.back(); int level = vec.size(); if(level>curLevel){ for(auto w:usedWords) dict.erase(w); usedWords.clear(); curLevel = level; } if(level<=minLen){ if(s==endWord){ ret.push_back(vec); minLen = min(minLen, level); }else if(level<minLen){ for(int i=0; i<n; ++i){ for(char c='a'; c<='z'; ++c){ string ss = s; ss[i] = c; if(dict.count(ss)==1){ usedWords.insert(ss); vec.push_back(ss); que.push(vec); vec.pop_back(); } } } } } } return ret; } };