niaokedaoren的方案中使用了一个前驱单词表，即记录每一个单词的前驱单词是哪些。这样在遍历完毕后，我们从end出发递归就能把所有路径生成出来。但是由于前驱单词表不能记录当前的层次信息，似乎我们没法完成去重的工作。这个方案的巧妙之处就在于它没有使用我们通常的队列保存待处理的单词，一个单词一个单词先进先出处理的方法，而是使用两个vector来模拟队列的操作。我们从vector 1中遍历单词进行转换尝试，发现能转换的单词后将其放入vector 2中。当vector 1中的单词处理完毕后即为一层处理完毕，它里面的单词就可以从字典里删去了。接着我们对vector 2进行同样处理，如此反复直到当前处理的vector中不再有单词。我们发现vector 1和vector 2在不断地交换正处理容器和待处理容器的身份，因此可以通过将其放入一个数组中，每次循环对数组下标值取反实现身份的交替.
class Solution {
public:
std::vector<std::vector<std::string> > findLadders(std::string start, std::string end, std::unordered_set<std::string> &dict)
{
result_.clear();
dict.insert(start);
dict.insert(end);
std::unordered_map<std::string, std::vector<std::string>> prevMap;
for(auto iter = dict.begin(); iter != dict.end(); ++iter)
{
prevMap[*iter] = std::vector<std::string>();
}
std::vector<std::unordered_set<std::string>> candidates(2);
// 为什么要用set 来存储，有讲究吗？ //我是这么考虑的，因为当前一层的某些节点可以从前一层的多个节点到达.
//用set,这样bfs的时候，多次加入这些节点，就没有事情了。
int current = 0;
int previous = 1;
candidates[current].insert(start);
while(true)
{
current = !current;
previous = !previous;
for (auto iter = candidates[previous].begin(); iter != candidates[previous].end(); ++iter)
{
dict.erase(*iter);
}
candidates[current].clear();
for(auto iter = candidates[previous].begin(); iter != candidates[previous].end(); ++iter)
{
std::string word = *iter;
for(size_t pos = 0; pos < iter->size(); ++pos)
{
char before=word[pos];
for(char i = 'a'; i <= 'z'; ++i)
{
if(before == i)
{
continue;
}
word[pos] = i;
if(dict.count(word) > 0)
{
prevMap[word].push_back(*iter);
candidates[current].insert(word);
}
}
word[pos]=before;
}
}
if (candidates[current].size() == 0)
{
return result_;
}
if (candidates[current].count(end))
{
break;
}
}
std::vector<std::string> path;
GeneratePath(prevMap, path, end);
return result_;
}
private:
void GeneratePath(std::unordered_map<std::string, std::vector<std::string>> &prevMap, std::vector<std::string>& path,
const std::string& word)
{
if (prevMap[word].size() == 0)
{
path.push_back(word);
std::vector<std::string> curPath = path;
reverse(curPath.begin(), curPath.end());
result_.push_back(curPath);
path.pop_back();
return;
}
path.push_back(word);
for (auto iter = prevMap[word].begin(); iter != prevMap[word].end(); ++iter)
{
GeneratePath(prevMap, path, *iter);
}
path.pop_back();
}
std::vector<std::vector<std::string>> result_;
};
//by anniekim, almost the same as the above code
class Solution {
public:
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
map<string, vector<string>> traces; // If A->C and B->C, then traces[C] contains A and B.
// This is used for recovering the paths.
vector<unordered_set<string>> level(2);
int cur = 0;
int prev = 1;
level[cur].insert(start);
dict.insert(end);
while (true)
{
prev = !prev;
cur = !cur;
level[cur].clear();
// remove visited words. IMPORTANT!
for (unordered_set<string>::iterator it = level[prev].begin(); it != level[prev].end(); ++it)
dict.erase(*it);
for (unordered_set<string>::iterator it = level[prev].begin(); it != level[prev].end(); ++it)
{
string word = *it;
for (size_t i = 0; i < word.size(); i++) {
char before = word[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == before)
continue;
word[i] = c;
if (dict.find(word) != dict.end()) {
traces[word].push_back(*it);
level[cur].insert(word);
}
}
word[i] = before;
}
}
if (level[cur].empty() || level[cur].count(end) > 0)
break;
}
vector<vector<string>> res;
vector<string> onePath;
if (!traces.empty())
buildResult(traces, res, onePath, end);
return res;
}
void buildResult(map<string, vector<string>> &traces, vector<vector<string>> &res, vector<string> &onePath, string word)
{
if (traces.count(word) == 0)
{
vector<string> copy(onePath);
copy.push_back(word);
reverse(copy.begin(), copy.end());
res.push_back(copy);
return;
}
const vector<string> &s = traces[word];
onePath.push_back(word);
for (vector<string>::const_iterator it = s.begin(); it != s.end(); ++it)
buildResult(traces, res, onePath, *it);
onePath.pop_back();
}
};
No comments:
Post a Comment