a**d 发帖数: 85 | 1 我的code就是每次往queue里加一个stack,然后BFS去找end,如果找到,那个stack就
包含所有的ladder。
能通过小测试,可是大的最后一个非常大的dict fail掉。
我觉得应该不是发生死循环了吧。每次我把之前level的words都加到hashset里防止下
面的重复。
请教大神指点一下为什么会fail掉。谢谢 | j********r 发帖数: 25 | 2 没有时间看你的是什么问题, 你参考一下如下程序吧:
int ladderLength(string start, string end, unordered_set &dict) {
int remaining = 1;
queue qou;
qou.push(start);
dict.erase(start);
int depth = 0;
while(qou.size() > 0) {
depth++;
int nextLevel = 0;
while(remaining >0) {
string s = qou.front();
qou.pop();
if (s == end) { return depth;}
for(int i = 0; i < s.length(); i++) {
for(int j = 'a'; j <='z'; j++) {
if (s[i] != j) {
string news = s;
news[i] = j;
if (dict.count(news) != 0) {
dict.erase(news);
qou.push(news);
nextLevel++;
}
}
}
}
remaining--;
}
remaining = nextLevel;
}
return 0;
}
【在 a**d 的大作中提到】 : 我的code就是每次往queue里加一个stack,然后BFS去找end,如果找到,那个stack就 : 包含所有的ladder。 : 能通过小测试,可是大的最后一个非常大的dict fail掉。 : 我觉得应该不是发生死循环了吧。每次我把之前level的words都加到hashset里防止下 : 面的重复。 : 请教大神指点一下为什么会fail掉。谢谢
|
|