[LeetCode 127] Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of
shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
Diffculty
Medium
Similar Problems
[LeetCode ] World Ladder II Medium
Analysis
http://www.cnblogs.com/ShaneZhang/p/3748494.html
class Solution {
public:
int ladderLength(std::string beginWord, std::string endWord, std::unordered_set &dict) {
if (beginWord == endWord)
return 1;
std::unordered_set words1, words2;
words1.insert(beginWord);
words2.insert(endWord);
dict.erase(beginWord);
dict.erase(endWord);
return ladderLengthHelper(words1, words2, dict, 1);
}
private:
int ladderLengthHelper(std::unordered_set &words1, std::unordered_set &words2, std::unordered_set &dict, int level) {
if (words1.empty())
return 0;
if (words1.size() > words2.size())
return ladderLengthHelper(words2, words1, dict, level);
std::unordered_set words3;
for (auto it = words1.begin(); it != words1.end(); ++it) {
std::string word = it;
for (auto ch = word.begin(); ch != word.end(); ++ch) {
char tmp = ch;
for (ch = 'a'; ch <= 'z'; ++(ch))
if (ch != tmp)
if (words2.find(word) != words2.end())
return level + 1;
else if (dict.find(word) != dict.end()) {
dict.erase(word);
words3.insert(word);
}
*ch = tmp;
}
}
return ladderLengthHelper(words2, words3, dict, level + 1);
}
};
// rewrite
class Solution {
public:
vector> findLadders(string start, string end, unordered_set &dict) {
vector > ladders;
vector ladder;
ladder.push_back(start);
unordered_set startWords, endWords;
startWords.insert(start);
endWords.insert(end);
unordered_map > children;
bool flip = true;
if (searchLadders(startWords, endWords, dict, children, flip))
genLadders(start, end, children, ladder, ladders);
return ladders;
}
private:
bool searchLadders(unordered_set& startWords, unordered_set& endWords,
unordered_set& dict, unordered_map >& children, bool flip) {
flip = !flip;
if (startWords.empty()) return false;
if (startWords.size() > endWords.size())
return searchLadders(endWords, startWords, dict, children, flip);
for (string word : startWords) dict.erase(word);
for (string word : endWords) dict.erase(word);
unordered_set intermediate;
bool done = false;
for (string word : startWords) {
int n = word.length();
string temp = word;
for (int p = 0; p < n; p++) {
char letter = word[p];
for (int i = 0; i < 26; i++) {
word[p] = 'a' + i;
if (endWords.find(word) != endWords.end()) {
done = true;
flip ? children[word].push_back(temp) : children[temp].push_back(word);
}
else if (!done && dict.find(word) != dict.end()) {
intermediate.insert(word);
flip ? children[word].push_back(temp) : children[temp].push_back(word);
}
}
word[p] = letter;
}
}
return done || searchLadders(endWords, intermediate, dict, children, flip);
}
void genLadders(string& start, string& end, unordered_map >& children,
vector& ladder, vector >& ladders) {
if (start == end) {
ladders.push_back(ladder);
return;
}
for (string child : children[start]) {
ladder.push_back(child);
genLadders(child, end, children, ladder, ladders);
ladder.pop_back();
}
}
};
// rewrite, no recursion needed
bool buildNexts(string start, string end, unordered_set &dict, map> &nexts) {
unordered_set head{start}, tail{end};
int len = start.size();
bool headIsFront = true, found = false;
while (!head.empty() && !tail.empty()) {
if (head.size() > tail.size()) {
swap(head,tail);
headIsFront = !headIsFront;
}
unordered_set tmp;
for (auto word: head) {
dict.erase(word);
string headWord = word;
for (int i = 0;i < len;++i) {
char letter = word[i];
for (int j = 'a';j <= 'z';++j) {
word[i] = j;
if (tail.find(word) != tail.end()) {
headIsFront ? nexts[headWord].push_back(word) : nexts[word].push_back(headWord);
found = true;
} else if (!found && dict.find(word) != dict.end()) {
headIsFront ? nexts[headWord].push_back(word) : nexts[word].push_back(headWord);
tmp.insert(word);
}
}
word[i] = letter;
}
}
if (found) return true;
for (auto word: tmp) // it's important to delete words here, but no other places!
dict.erase(word);
head = tmp;
}
return false;
}
void buildAns(string start, string end, map> &nexts, vector &path, vector> &ans) {
if (start == end) {
ans.push_back(path);
return;
}
for (auto s :nexts[start]) {
path.push_back(s);
buildAns(s, end, nexts, path, ans);
path.pop_back();
}
}
vector> findLadders(string start, string end, unordered_set &dict) {
vector> ans;
vector path(1, start);;
map> nexts;
if (buildNexts(start,end,dict,nexts))
buildAns(start,end,nexts,path,ans);
return ans;
}