126. Word Ladder II
從單詞 beginWord 到單詞 endWord 的轉換序列使用字典 wordList 是一個單詞序列 beginWord -> s1 -> s2 -> ... -> sk，滿足以下條件：
每一對相鄰的單詞僅差一個字母。 每個 si（1 <= i <= k）都在 wordList 中。注意，beginWord 不需要在 wordList 中。 sk 等於 endWord。 給定兩個單詞 beginWord 和 endWord，以及一個字典 wordList，返回所有從 beginWord 到 endWord 的最短轉換序列，或者如果不存在這樣的序列則返回一個空列表。每個序列應該以單詞列表的形式返回 [beginWord, s1, s2, ..., sk]。
範例：
輸入：beginWord = "hit"，endWord = "cog"，wordList = ["hot","dot","dog","lot","log","cog"] 輸出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] 解釋：有兩個最短轉換序列： "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog"
Python
class Solution:
def findLadders(
self, beginWord: str, endWord: str, wordList: List[str]
) -> List[List[str]]:
def neighbors(word):
for i in range(len(word)):
for char in "abcdefghijklmnopqrstuvwxyz":
yield word[:i] + char + word[i + 1 :]
i = 1
words = {beginWord: lambda: [[beginWord]]}
unvisited = set(wordList)
while words and endWord not in words:
i += 1
new_words = defaultdict(lambda: lambda: [])
for s in words:
for ss in neighbors(s):
if ss in unvisited:
def get_seqs(capture=(ss, new_words[ss], words[s])):
ss, ss_get_seqs, s_get_seqs = capture
seqs = ss_get_seqs()
for seq in s_get_seqs():
seq.append(ss)
seqs.append(seq)
return seqs
new_words[ss] = get_seqs
words = new_words
unvisited -= words.keys()
return words[endWord]()
17.2MB, 78ms
C++
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord,
vector<string>& wordList) {
int n=wordList.size();
unordered_set<string> uset;
for(auto const &it:wordList){
if(it!=beginWord) uset.insert(it);
}
queue<string> q;
q.push(beginWord);
vector<pair<string,int>> levels;
int cnt=0;
bool flag=false;
while(!q.empty()){
int sz=q.size();
for(int i=0;i<sz;i++){
string node=q.front();
q.pop();
levels.push_back({node,cnt});
if(node==endWord){
flag=true;
break;
}
for(int i=0;i<node.length();i++){
char original=node[i];
for(char j='a';j<='z';j++){
if(original==j) continue;
node[i]=j;
if(uset.find(node)!=uset.end()){
q.push(node);
uset.erase(node);
}
}
node[i]=original;
}
}
if(flag) break;
cnt++;
}
vector<vector<string>> ans;
if(!flag){
return ans;
}
vector<pair<string,int>>::reverse_iterator it=levels.rbegin();
vector<string> vec;
dfs(endWord,levels,ans,vec,it,cnt,beginWord);
return ans;
}
private:
void dfs(string str,vector<pair<string,int>> &levels,vector<vector<string>>
&ans,vector<string> &vec,vector<pair<string,int>>::reverse_iterator it,
int cnt,string &beginWord){
if(str==beginWord){
vec.push_back(str);
reverse(vec.begin(),vec.end());
ans.push_back(vec);
reverse(vec.begin(),vec.end());
vec.pop_back();
return;
}
while(it!=levels.rend() && it->second==cnt){
it++;
}
while(it!=levels.rend() && it->second==cnt-1){
if(isPossible(str,it->first)){
vec.push_back(str);
dfs(it->first,levels,ans,vec,it,cnt-1,beginWord);
vec.pop_back();
}
it++;
}
}
bool isPossible(string str1,string str2){
int n=str1.length();
int diff=0;
for(int i=0;i<n;i++){
if(str1[i]!=str2[i]){
diff++;
}
if(diff>1) return false;
}
return true;
}
};
12.04MB, 11ms
Javascript
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {string[][]}
*/
var findLadders = function(beginWord, endWord, wordList) {
function* neighbors(word) {
for (let i = 0; i < word.length; i++) {
for (let char of 'abcdefghijklmnopqrstuvwxyz') {
yield word.slice(0, i) + char + word.slice(i + 1);
}
}
}
let i = 1;
let words = { [beginWord]: () => [[beginWord]] };
let unvisited = new Set(wordList);
while (Object.keys(words).length > 0 && !(endWord in words)) {
i++;
let newWords = {};
for (let s in words) {
for (let ss of neighbors(s)) {
if (unvisited.has(ss)) {
if (!(ss in newWords)) {
newWords[ss] = () => [];
}
let capture = [ss, newWords[ss], words[s]];
newWords[ss] = () => {
let [ss, ssGetSeqs, sGetSeqs] = capture;
let seqs = ssGetSeqs();
for (let seq of sGetSeqs()) {
seq = [...seq, ss];
seqs.push(seq);
}
return seqs;
};
}
}
}
words = newWords;
for (let word of Object.keys(words)) {
unvisited.delete(word);
}
}
return endWord in words ? words[endWord]() : [];
};
59.03MB, 101ms
