Word Ladder II
Given two words (startandend), and a dictionary, find all shortest transformation sequence(s) fromstarttoend, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start="hit"
end="cog"
dict=["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
Leetcode 第一难题,六星级! 帆船酒店来了!
难点考点:
1 知道什么时候去掉重复,会使用set容器避免重复
2 高级层序遍历树应用
3 适当时候去掉字典中的单词避免重复
4 知道什么时候结束层序
5 利用高级数据结构保存结果,本程序使用unordered_map<string, vector<string> >
6 使用递归回溯法,利用高级数据结构,构造最终结果
每一点几乎都可以成为一个大题,都糅合在一起了,加上各个细节,那么就构成了一个六星级难题了。
注意细节:
1 上一层的单词要删掉,否则会有回路,形成无线循环
2 下一层保存单词不能重复,否则会有很多多余的单词处理,造成time limit excessed
新思维解决问题:
子节点可以重复,但是只保留一个子节点,不过要保留这个子节点的多个父母节点,但是子节点只能保留一份。
要怎么完成这个操作呢?
1 使用set保留子节点
2 使用map<string, vector<string> > 保留父母节点,这样确保只有一个string子节点,而可以有多个父母节点vector<string>
形成path的时候,因为最终根节点肯定是start,所以一个孩子节点分别从多个父母节点回溯,都必然会到达start根节点
//2014-2-18 update
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict)
{
vector<vector<string> > rs;
unordered_map<string, vector<string> > ump_sv;
dict.erase(start);
dict.erase(end);
vector<string> qu[2];
set<string> sst;
qu[0].push_back(start);
bool idx = false;
bool finished = false;
while (!qu[idx].empty())
{
while (!qu[idx].empty())
{
string s = qu[idx].back();
for (int i = 0; i < s.length(); i++)
{
char a = s[i];
for (char az = 'a'; az <= 'z'; az++)
{
s[i] = az;
if (s == end)
{
finished = true;
ump_sv[s].push_back(qu[idx].back());
}
else if (dict.count(s))
{
ump_sv[s].push_back(qu[idx].back());
qu[!idx].push_back(s);
}
}
s[i] = a;
}//for
qu[idx].pop_back();
}//while
if (finished) break;
idx = !idx;
sst.clear();
sst.insert(qu[idx].begin(), qu[idx].end());
qu[idx].assign(sst.begin(), sst.end());
for (auto x:qu[idx]) dict.erase(x);
}//while
if (!ump_sv.count(end)) return rs;
vector<string> tmp(1, end);
constructLadder(rs, tmp, ump_sv, start, end);
return rs;
}
void constructLadder(vector<vector<string> > &rs, vector<string> &tmp,
unordered_map<string, vector<string> > &ump_sv, string &start, string &cur)
{
if (cur == start)
{
rs.push_back(tmp);
reverse(rs.back().begin(), rs.back().end());
return;
}
vector<string> v = ump_sv[cur];
for (int i = 0; i < v.size(); i++)
{
tmp.push_back(v[i]);
constructLadder(rs, tmp, ump_sv, start, v[i]);
tmp.pop_back();
}
}
分享到:
相关推荐
126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】
经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode卡leetcode_practices_learncard_recursionii 我的 leetcode 递归练习 ii 学习卡在 100% 完成 :) 我的 Java8 备忘单:
leetcode中文版
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
6 Word Ladder II 29 7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 ...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
自己做leecode题目的总结,做个分享从事服务端开发,少不了要接触网络编程。epoll作为linux下高性能网络服务器的必备技术至关重要,nginx、redis、skynet和大部分游戏服务器都使用到这一多路复用技术。...