h**********y
发帖数: 1293 | | p*****2
发帖数: 21240 | | f*******t
发帖数: 7549 | 3 为什么？
其实可以写一下，实在过不了leetcode large case就算了
【在 p*****2 的大作中提到】
: 我认为这题可以skip
| h**********y
发帖数: 1293 | 4 大牛就大概说说general的做法呗。。。
【在 p*****2 的大作中提到】
: 我认为这题可以skip
| p*****2
发帖数: 21240 | 5
因为Leetcode就是准备面试用的，不是玩竞赛的。对于面试来说，这题不是原题，原题
在CC150里。面试中遇到的也是CC150的原题。从算法和竞赛来讲，最短路径一般都是找
一条的，参见Dijkstra， 或者找所有pair的，参见Floyd-Warshall，但是所有pair也
是找最小cost而不是所有路径。另外每个pair只需要一个最短就可以了。因此word
ldadder II这题出的很诡异。既不是面试题，又不是竞赛题，我不知道有什么特别的意
义。
通常竞赛来说，输入的规模，时间，空间的要求都说的很详细。一般不需要写code就可
以把算法想的八九不离十，但是这题感觉就是要去死磕，我不太清楚，花那么多时间的
收获是什么。当然你要是觉得值得去做也没什么问题。我肯定不会花这个时间了。
【在 f*******t 的大作中提到】
: 为什么？
: 其实可以写一下，实在过不了leetcode large case就算了
| p*****2
发帖数: 21240 | 6
你去看看CC150最后一章里有面试的原题，答案也有。面试就够了。
【在 h**********y 的大作中提到】
: 大牛就大概说说general的做法呗。。。
| h**********y
发帖数: 1293 | 7 明白了。谢谢大牛指点。
【在 p*****2 的大作中提到】
:
: 你去看看CC150最后一章里有面试的原题，答案也有。面试就够了。
| i**********e
发帖数: 1145 | 8 我不认同你所说的。
首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
就够了。
对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
你的思维灵活贯通就更好了。
生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
所有的答案。
竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
只是我一点点的两分钱，just my 2 cents。
【在 p*****2 的大作中提到】
:
: 你去看看CC150最后一章里有面试的原题，答案也有。面试就够了。
| h***i
发帖数: 1970 | 9 要是竞赛的话，这道题的正解应该是A*
【在 i**********e 的大作中提到】
: 我不认同你所说的。
: 首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
: 就够了。
: 对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
: impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
: 你的思维灵活贯通就更好了。
: 生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
: 所有的答案。
: 竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
: 只是我一点点的两分钱，just my 2 cents。
| p*****2
发帖数: 21240 | 10
我个人希望做Leetcode的OJ能够接近做面试题的感觉。否则的话还不如去做TC和CF等等
呢。如果真是愿意死磕的话，去做IS就行了。前边有人说了这题做了5天还不知道怎么
回事。我不太清楚花5天是不是值得。面试能碰到这种要求的概率我觉得很低了，不如
把时间用来做高频题。还有就算面试出现了，我觉得也仅仅限于讨论阶段，不太可能要
求面试者在短短的时间把这题可以做到可以pass OJ。不过这也是我的个人观点，我也
常常犯错误，我理解有问题的可能性也是蛮大的。
【在 i**********e 的大作中提到】
: 我不认同你所说的。
: 首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
: 就够了。
: 对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
: impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
: 你的思维灵活贯通就更好了。
: 生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
: 所有的答案。
: 竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
: 只是我一点点的两分钱，just my 2 cents。
| | | p*****2
发帖数: 21240 | 11
还有就是大牛能不能讲讲求所有最短路径的general算法是什么呢？
【在 i**********e 的大作中提到】
: 我不认同你所说的。
: 首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
: 就够了。
: 对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
: impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
: 你的思维灵活贯通就更好了。
: 生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
: 所有的答案。
: 竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
: 只是我一点点的两分钱，just my 2 cents。
| p****e
发帖数: 3548 | 12 修改下BFS也可以，要记下路径就行
用'a'-'z'方法再写了一个
大数据: 750ms
class Solution {
public:
void getrows(vector, unordered_map::
iterator> > &path,
int col, vector &row, vector > &
ret){
row.push_back(path[col].second->first);
vector & cp = path[col].first;
for(int i=0; i
if(cp[i] < 0){
reverse(row.begin(), row.end());
ret.push_back(row);
reverse(row.begin(), row.end());
break;
}
else
getrows(path, cp[i], row, ret);
}
row.pop_back();
}
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
vector, unordered_map::iterator> >
path;
unordered_map useddict;
path.push_back(make_pair(vector(1,-1),
useddict.insert(make_pair(start, 0)).first));
bool found = false;
int pathindex = 0;
int pathsize = 0;
do{
pathsize = path.size();
for(; pathindex < pathsize; pathindex++){
string s = path[pathindex].second->first;
bool sf = false;
for(int i=0; i < s.size() && !sf; ++i){
char o = s[i];
for(char c='a'; c<='z'; ++c){
if(c==o) continue;
s[i] = c;
if(s == end){
found = true;
sf = true;
vector row(1, end);
getrows(path, pathindex, row, ret);
break;
}
if(!found && dict.count(s)){
auto it = useddict.find(s);
if(it == useddict.end())
path.push_back(make_pair(vector(1,
pathindex),
useddict.insert(make_pair(s, path.size()
)).first));
else if(it->second >= pathsize)
path[it->second].first.push_back(
pathindex);
}
}
s[i] = o;
}
}
if(found) break;
}
while(pathsize
return ret;
}
};
【在 h**********y 的大作中提到】
: 似乎可以修改下BFS来做？
: IDS？
| s*w
发帖数: 729 | 13 1. 去掉 BFS 中 search 到 end 要退出这段
2. BFS 中 current node 的 neighbors 里，本来只考虑没发现的 node (white node)
, 要改成也考虑 gray node (如果 gray node 深度是当前node 深度+1，就说明该
gray node 的 parent 除了它以前的 parent (把它从白变灰的那个) 也包括了当前
node
3. 每个 node 有若干 parent, 从 end 递归上去就可重建所有最短 path
【在 h**********y 的大作中提到】
: 似乎可以修改下BFS来做？
: IDS？
| h**********y
发帖数: 1293 | | p*****2
发帖数: 21240 | | f*******t
发帖数: 7549 | 16 为什么？
其实可以写一下，实在过不了leetcode large case就算了
【在 p*****2 的大作中提到】
: 我认为这题可以skip
| h**********y
发帖数: 1293 | 17 大牛就大概说说general的做法呗。。。
【在 p*****2 的大作中提到】
: 我认为这题可以skip
| p*****2
发帖数: 21240 | 18
因为Leetcode就是准备面试用的，不是玩竞赛的。对于面试来说，这题不是原题，原题
在CC150里。面试中遇到的也是CC150的原题。从算法和竞赛来讲，最短路径一般都是找
一条的，参见Dijkstra， 或者找所有pair的，参见Floyd-Warshall，但是所有pair也
是找最小cost而不是所有路径。另外每个pair只需要一个最短就可以了。因此word
ldadder II这题出的很诡异。既不是面试题，又不是竞赛题，我不知道有什么特别的意
义。
通常竞赛来说，输入的规模，时间，空间的要求都说的很详细。一般不需要写code就可
以把算法想的八九不离十，但是这题感觉就是要去死磕，我不太清楚，花那么多时间的
收获是什么。当然你要是觉得值得去做也没什么问题。我肯定不会花这个时间了。
【在 f*******t 的大作中提到】
: 为什么？
: 其实可以写一下，实在过不了leetcode large case就算了
| p*****2
发帖数: 21240 | 19
你去看看CC150最后一章里有面试的原题，答案也有。面试就够了。
【在 h**********y 的大作中提到】
: 大牛就大概说说general的做法呗。。。
| h**********y
发帖数: 1293 | 20 明白了。谢谢大牛指点。
【在 p*****2 的大作中提到】
:
: 你去看看CC150最后一章里有面试的原题，答案也有。面试就够了。
| | | i**********e
发帖数: 1145 | 21 我不认同你所说的。
首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
就够了。
对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
你的思维灵活贯通就更好了。
生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
所有的答案。
竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
只是我一点点的两分钱，just my 2 cents。
【在 p*****2 的大作中提到】
:
: 你去看看CC150最后一章里有面试的原题，答案也有。面试就够了。
| h***i
发帖数: 1970 | 22 要是竞赛的话，这道题的正解应该是A*
【在 i**********e 的大作中提到】
: 我不认同你所说的。
: 首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
: 就够了。
: 对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
: impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
: 你的思维灵活贯通就更好了。
: 生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
: 所有的答案。
: 竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
: 只是我一点点的两分钱，just my 2 cents。
| p*****2
发帖数: 21240 | 23
我个人希望做Leetcode的OJ能够接近做面试题的感觉。否则的话还不如去做TC和CF等等
呢。如果真是愿意死磕的话，去做IS就行了。前边有人说了这题做了5天还不知道怎么
回事。我不太清楚花5天是不是值得。面试能碰到这种要求的概率我觉得很低了，不如
把时间用来做高频题。还有就算面试出现了，我觉得也仅仅限于讨论阶段，不太可能要
求面试者在短短的时间把这题可以做到可以pass OJ。不过这也是我的个人观点，我也
常常犯错误，我理解有问题的可能性也是蛮大的。
【在 i**********e 的大作中提到】
: 我不认同你所说的。
: 首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
: 就够了。
: 对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
: impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
: 你的思维灵活贯通就更好了。
: 生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
: 所有的答案。
: 竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
: 只是我一点点的两分钱，just my 2 cents。
| p*****2
发帖数: 21240 | 24
还有就是大牛能不能讲讲求所有最短路径的general算法是什么呢？
【在 i**********e 的大作中提到】
: 我不认同你所说的。
: 首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
: 就够了。
: 对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
: impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
: 你的思维灵活贯通就更好了。
: 生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
: 所有的答案。
: 竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
: 只是我一点点的两分钱，just my 2 cents。
| p****e
发帖数: 3548 | 25 修改下BFS也可以，要记下路径就行
用'a'-'z'方法再写了一个
大数据: 750ms
class Solution {
public:
void getrows(vector, unordered_map::
iterator> > &path,
int col, vector &row, vector > &
ret){
row.push_back(path[col].second->first);
vector & cp = path[col].first;
for(int i=0; i
if(cp[i] < 0){
reverse(row.begin(), row.end());
ret.push_back(row);
reverse(row.begin(), row.end());
break;
}
else
getrows(path, cp[i], row, ret);
}
row.pop_back();
}
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
vector, unordered_map::iterator> >
path;
unordered_map useddict;
path.push_back(make_pair(vector(1,-1),
useddict.insert(make_pair(start, 0)).first));
bool found = false;
int pathindex = 0;
int pathsize = 0;
do{
pathsize = path.size();
for(; pathindex < pathsize; pathindex++){
string s = path[pathindex].second->first;
bool sf = false;
for(int i=0; i < s.size() && !sf; ++i){
char o = s[i];
for(char c='a'; c<='z'; ++c){
if(c==o) continue;
s[i] = c;
if(s == end){
found = true;
sf = true;
vector row(1, end);
getrows(path, pathindex, row, ret);
break;
}
if(!found && dict.count(s)){
auto it = useddict.find(s);
if(it == useddict.end())
path.push_back(make_pair(vector(1,
pathindex),
useddict.insert(make_pair(s, path.size()
)).first));
else if(it->second >= pathsize)
path[it->second].first.push_back(
pathindex);
}
}
s[i] = o;
}
}
if(found) break;
}
while(pathsize
return ret;
}
};
【在 h**********y 的大作中提到】
: 似乎可以修改下BFS来做？
: IDS？
| s*w
发帖数: 729 | 26 1. 去掉 BFS 中 search 到 end 要退出这段
2. BFS 中 current node 的 neighbors 里，本来只考虑没发现的 node (white node)
, 要改成也考虑 gray node (如果 gray node 深度是当前node 深度+1，就说明该
gray node 的 parent 除了它以前的 parent (把它从白变灰的那个) 也包括了当前
node
3. 每个 node 有若干 parent, 从 end 递归上去就可重建所有最短 path
【在 h**********y 的大作中提到】
: 似乎可以修改下BFS来做？
: IDS？
| u******g
发帖数: 89 | 27 这题是不是测试数据有问题啊……
start = "hot",
end = "dog",
dict = ["hot","cog","dog","tot","hog","hop","pot","dot"],
expected = [["hot","dot","dog"]]
my output= [["hot","dot","dog"],["hot","hog","dog"]]
他题目里明明是说
" find all shortest transformation sequence(s) from start to end"啊 | j******s
发帖数: 48 | 28 Hi,请问word ladder II 的测试数据是不有点问题么？
对于输入:
"hit", "cog", ["hot","cog","dot","dog","hit","lot","log"]
我的输出是
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"],["hot","dot
","lot","log","cog"],["hot","dot","dog","log","cog"]]
测试数据输出的是
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
根据题目的定义应该是都可以的吧？
嗯嗯，我知道答案是不是正确不是特别重要，只是这道题我花了很多时间对比BFS,DFS,
IDS以及实现他们的一些不同方式，所以希望可以求证一下而已。
附贴上我的代码
class Solution {
private:
class Node{
public:
string word;
vector parents;
int depth;
int childCount;
Node(string w,int d,int c=0):word(w),depth(d),childCount(c){}
~Node()
{
for(int i=0;i
{
if(--(parents[i]->childCount) == 0)
delete parents[i];
}
}
};
public:
vector> findLadders(string start, string end, unordered_
set &dict)
{
vector> result;
map visited;
map visiting;
queue frontier;
Node* st = new Node(start,1);
visiting[start] = st;
frontier.push(st);
bool found = start==end;
int cp = 0;
while(!frontier.empty() && (!found || (found && cp == frontier.front
()->depth)))
{
Node* node = frontier.front();
frontier.pop();
visited[node->word] = node;
visiting.erase(node->word);
cp = node->depth;
string newWord(node->word);
for(int i=0;i
{
char c = newWord[i];
for(char j='a';j<='z';j++)
{
newWord[i] = j;
if(dict.count(newWord)>0 && visited.count(newWord)==0)
{
if(newWord == end) found = true;
if(visiting.count(newWord)>0){
(visiting[newWord]->parents).push_back(node);
}else{
Node* newNode = new Node(newWord,cp+1);
(newNode->parents).push_back(node);
visiting[newWord] = newNode;
frontier.push(newNode);
}
node->childCount++;
}
}
newWord[i] = c;
}
if(node->childCount == 0) delete node;
}
if(visiting.count(end)>0)
{
vector path(visiting[end]->depth,"");
addToResult(result,path,visiting[end]->depth-1,visiting[end]);
}
while(!frontier.empty()){delete frontier.front();frontier.pop();}
return result;
}
void addToResult(vector> &result,vector &path,
int depth,Node* node)
{
path[depth] = node->word;
if(depth == 0)
{
result.push_back(path);
return;
}
vector parents = node->parents;
for(int i=0;i
addToResult(result,path,depth-1,parents[i]);
}
};
【在 i**********e 的大作中提到】
: 我不认同你所说的。
: 首先，准备面试必须要想得深入，一道题可以有很多变种和扩展，不是仅仅做对这道题
: 就够了。
: 对，这道题的扩展是我自己想出来的。面试你很快做出来一道题了，很好，但这不够
: impress。通常一个好的面试官会问许多的follow up，你在 follow up 的时候能展示
: 你的思维灵活贯通就更好了。
: 生活中很多时候都必须列举所有可能性的。如果这是个真实游戏，玩家还是希望能看到
: 所有的答案。
: 竞赛题之所以只输出一个最短的 是仅仅方便检查程序的输出而已。
: 只是我一点点的两分钱，just my 2 cents。
|
|
