x*o
2 楼
客观地分析一下。
岳灵珊：会武功、会做饭、会女工、名声好、名望高。
任盈盈：会吹箫。
只要是男人，就该选任盈盈！
岳灵珊：会武功、会做饭、会女工、名声好、名望高。
任盈盈：会吹箫。
只要是男人，就该选任盈盈！
w*x
3 楼
这题怎么那么别扭，原来目标单词不在字典里...
还有我咋超时了...
还有我咋超时了...
R*a
4 楼
名声和名望啥区别？
知名度显然任大小姐高啊
【在 x****o 的大作中提到】
: 客观地分析一下。
: 岳灵珊：会武功、会做饭、会女工、名声好、名望高。
: 任盈盈：会吹箫。
: 只要是男人，就该选任盈盈！
知名度显然任大小姐高啊
【在 x****o 的大作中提到】
: 客观地分析一下。
: 岳灵珊：会武功、会做饭、会女工、名声好、名望高。
: 任盈盈：会吹箫。
: 只要是男人，就该选任盈盈！
i*e
5 楼
贴贴你代码？
d*o
6 楼
武功，名望岳灵珊比任盈盈差太远了
名声这东西令狐冲根本不care
做饭女红两人估计半斤八两
【在 x****o 的大作中提到】
: 客观地分析一下。
: 岳灵珊：会武功、会做饭、会女工、名声好、名望高。
: 任盈盈：会吹箫。
: 只要是男人，就该选任盈盈！
名声这东西令狐冲根本不care
做饭女红两人估计半斤八两
【在 x****o 的大作中提到】
: 客观地分析一下。
: 岳灵珊：会武功、会做饭、会女工、名声好、名望高。
: 任盈盈：会吹箫。
: 只要是男人，就该选任盈盈！
w*x
7 楼
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
unordered_set visited;
visited.insert(start);
queue que;
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set::iterator it = dict.begin();
it != dict.end(); it++)
{
if (visited.find(*it) == visited.end() && canChng(*it,
strCur))
{
que.push(*it);
visited.insert(*it);
nNextNum++;
}
}
if (canChng(end, strCur))
return nCurLev+1;
if (nCurNum <= 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return 0;
}
bool canChng(string a, string b)
{
if (a.length() != b.length())
return false;
bool bDiff = false;
for (int i = 0; i < a.length(); i++)
{
if (a.at(i) != b.at(i))
{
if (bDiff)
return false;
bDiff = true;
}
}
return bDiff;
}
};
public:
int ladderLength(string start, string end, unordered_set
unordered_set
visited.insert(start);
queue
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set
it != dict.end(); it++)
{
if (visited.find(*it) == visited.end() && canChng(*it,
strCur))
{
que.push(*it);
visited.insert(*it);
nNextNum++;
}
}
if (canChng(end, strCur))
return nCurLev+1;
if (nCurNum <= 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return 0;
}
bool canChng(string a, string b)
{
if (a.length() != b.length())
return false;
bool bDiff = false;
for (int i = 0; i < a.length(); i++)
{
if (a.at(i) != b.at(i))
{
if (bDiff)
return false;
bDiff = true;
}
}
return bDiff;
}
};
R*a
8 楼
做饭肯定是岳灵珊强。
一个是当年令狐冲思过的时候小师妹给他单做过饭吧。
另外一个是她和劳德诺去福建卧底的时候开的是饭馆，
饭馆员工就她和劳德诺两个人，总不好说是劳德诺一个人包圆了所有做饭吧。
任大小姐有记录的一次做饭是烤青蛙，还给烤糊了
【在 d****o 的大作中提到】
: 武功，名望岳灵珊比任盈盈差太远了
: 名声这东西令狐冲根本不care
: 做饭女红两人估计半斤八两
一个是当年令狐冲思过的时候小师妹给他单做过饭吧。
另外一个是她和劳德诺去福建卧底的时候开的是饭馆，
饭馆员工就她和劳德诺两个人，总不好说是劳德诺一个人包圆了所有做饭吧。
任大小姐有记录的一次做饭是烤青蛙，还给烤糊了
【在 d****o 的大作中提到】
: 武功，名望岳灵珊比任盈盈差太远了
: 名声这东西令狐冲根本不care
: 做饭女红两人估计半斤八两
i*e
9 楼
如果字典很大怎么办？
m*f
10 楼
岳灵珊性取向可议，任盈盈就不同，主动远离东方不败。
p*p
11 楼
large TLE了
不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list queue;
set visited;
map stepMap;
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string s = queue.front();
queue.pop_front();
if (diffByOne(s, end)) return stepMap[s] + 1;
int currentStep = stepMap[s];
for (string strInDict : dict) {
if (visited.find(strInDict) != visited.end()) continue;
if (diffByOne(s, strInDict)) {
queue.push_back(strInDict);
visited.insert(strInDict);
stepMap[strInDict] = currentStep + 1;
}
}
}
return 0;
}
bool diffByOne(string &s1, string &s2) {
if (s1.size() != s2.size()) return false;
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++diff;
if (diff > 1) return false;
}
return diff == 1 ? true : false;
}
};
不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
list
set
map
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string s = queue.front();
queue.pop_front();
if (diffByOne(s, end)) return stepMap[s] + 1;
int currentStep = stepMap[s];
for (string strInDict : dict) {
if (visited.find(strInDict) != visited.end()) continue;
if (diffByOne(s, strInDict)) {
queue.push_back(strInDict);
visited.insert(strInDict);
stepMap[strInDict] = currentStep + 1;
}
}
}
return 0;
}
bool diffByOne(string &s1, string &s2) {
if (s1.size() != s2.size()) return false;
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++diff;
if (diff > 1) return false;
}
return diff == 1 ? true : false;
}
};
b*a
12 楼
一个白道，一个 underworld
【在 R***a 的大作中提到】
: 名声和名望啥区别？
: 知名度显然任大小姐高啊
【在 R***a 的大作中提到】
: 名声和名望啥区别？
: 知名度显然任大小姐高啊
i*e
13 楼
关于怎么测下一步是不是合法：
每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
了。
每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
了。
q*l
14 楼
令狐冲比较憨，得配个智商情商都高的。
a*o
15 楼
我来贴个能过的,比较丑,大家见谅...
int ladderLength(string start, string end, tr1::unordered_set &dict)
{
set contain;
int count = 1;
queue list[2];
list[0].push(start);
while (list[0].size()!= 0 || list[1].size()!=0){
int oldlist = 0;
int newlist = 1;
if (list[0].size()== 0){
oldlist = 1;
newlist = 0;
}
while (list[oldlist].size() != 0){
string curr = list[oldlist].front();
list[oldlist].pop();
if (contain.count(curr) > 0) continue;
contain.insert(curr);
for (int i = 0; i< curr.size(); i++){
for (int j = 0; j<26; j++){
char temp = curr[i];
char newtemp = (char) ('a'+j);
if (temp != newtemp){
string newcurr = curr;
newcurr[i] = newtemp;
if (newcurr == end) return count
+1;
if (dict.count(newcurr)> 0){
list[newlist].push(
newcurr);
}
}
}
}
}
count ++;
}
return 0;
}
【在 p****e 的大作中提到】
: rt
int ladderLength(string start, string end, tr1::unordered_set
{
set
int count = 1;
queue
list[0].push(start);
while (list[0].size()!= 0 || list[1].size()!=0){
int oldlist = 0;
int newlist = 1;
if (list[0].size()== 0){
oldlist = 1;
newlist = 0;
}
while (list[oldlist].size() != 0){
string curr = list[oldlist].front();
list[oldlist].pop();
if (contain.count(curr) > 0) continue;
contain.insert(curr);
for (int i = 0; i< curr.size(); i++){
for (int j = 0; j<26; j++){
char temp = curr[i];
char newtemp = (char) ('a'+j);
if (temp != newtemp){
string newcurr = curr;
newcurr[i] = newtemp;
if (newcurr == end) return count
+1;
if (dict.count(newcurr)> 0){
list[newlist].push(
newcurr);
}
}
}
}
}
count ++;
}
return 0;
}
【在 p****e 的大作中提到】
: rt
f*c
16 楼
岳灵珊太各色
w*x
17 楼
) {
这个也超时了
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list
: set
: map
f*n
18 楼
显然老劳做，饭菜酒水都不齐，不是长期开始馆子。只记得小事没送饭不记得做饭了。
【在 R***a 的大作中提到】
: 做饭肯定是岳灵珊强。
: 一个是当年令狐冲思过的时候小师妹给他单做过饭吧。
: 另外一个是她和劳德诺去福建卧底的时候开的是饭馆，
: 饭馆员工就她和劳德诺两个人，总不好说是劳德诺一个人包圆了所有做饭吧。
: 任大小姐有记录的一次做饭是烤青蛙，还给烤糊了
【在 R***a 的大作中提到】
: 做饭肯定是岳灵珊强。
: 一个是当年令狐冲思过的时候小师妹给他单做过饭吧。
: 另外一个是她和劳德诺去福建卧底的时候开的是饭馆，
: 饭馆员工就她和劳德诺两个人，总不好说是劳德诺一个人包圆了所有做饭吧。
: 任大小姐有记录的一次做饭是烤青蛙，还给烤糊了
i*e
19 楼
是比较奇怪，但仔细看好规则：
Each intermediate word must exist in the dictionary
start 和 end 都不是 intermediate word，所以字典可有可无。
) {
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set &dict) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list queue;
: set visited;
: map stepMap;
Each intermediate word must exist in the dictionary
start 和 end 都不是 intermediate word，所以字典可有可无。
) {
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list
: set
: map
w*x
20 楼
没看明白..
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
a*o
21 楼
就是先变再到查词典查 VS. 先从词典抓一个再查是不是只变了一个字母
【在 w****x 的大作中提到】
:
: 没看明白..
【在 w****x 的大作中提到】
:
: 没看明白..
i*e
22 楼
你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
【在 w****x 的大作中提到】
:
: 没看明白..
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
【在 w****x 的大作中提到】
:
: 没看明白..
w*x
23 楼
这个啊，没意思，太tricky了
【在 a***o 的大作中提到】
: 就是先变再到查词典查 VS. 先从词典抓一个再查是不是只变了一个字母
a*o
24 楼
leetcode大侠,能不能指点一下这个ladder2怎么做啊
DFS能过么?还是要BFS+记路径?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
DFS能过么?还是要BFS+记路径?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
w*x
25 楼
感觉正常的思路是有一步pre processing,就是先把dict建图，
然后后续的查询ladder从建好的图为出发点。
这个图可以用map表示
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
w*x
26 楼
用map
wordladder2 太麻烦了，不做了,string的hash map还得自己写
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
a*o
27 楼
是啊,搞了个递归超时了,
看来得上bfs+map,不知道会不会超mem
【在 w****x 的大作中提到】
:
: 用map>记录路径，然后递归输出吧
: wordladder2 太麻烦了，不做了,string的hash map还得自己写
看来得上bfs+map,不知道会不会超mem
【在 w****x 的大作中提到】
:
: 用map
: wordladder2 太麻烦了，不做了,string的hash map还得自己写
i*e
28 楼
DFS 肯定过不了。最长的ladder length 是 42。
BFS + 记路径是正解。
但怎么记路径使得空间少 + 重建路径是比较tricky。
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
BFS + 记路径是正解。
但怎么记路径使得空间少 + 重建路径是比较tricky。
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
a*o
29 楼
多谢,再去琢磨琢磨
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
w*x
30 楼
BFS然后构建map
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
i*e
31 楼
牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
start。其实输出
路径不用递归也可以，比较麻烦一些就是了。
【在 w****x 的大作中提到】
:
: BFS然后构建map>结构，输出路径还是得递归吧
start。其实输出
路径不用递归也可以，比较麻烦一些就是了。
【在 w****x 的大作中提到】
:
: BFS然后构建map
w*x
32 楼
你饶了我吧。。。
是不是有个unordered_map可以hash string??
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
i*e
33 楼
你要的是 unordered_multimap 吧。
一个 key 可以 map 到好几个 value.
一个 key 可以 map 到好几个 value.
p*p
34 楼
原来是这样
这题在CC上有，但是没仔细看过，现在回头看原来是这么回事，学习了
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
这题在CC上有，但是没仔细看过，现在回头看原来是这么回事，学习了
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
f*t
35 楼
public int ladderLength(String start, String end, HashSet dict) {
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet used = new HashSet();
HashSet cur = new HashSet();
cur.add(start);
while(!cur.isEmpty()) {
HashSet newCur = new HashSet();
dist++;
for (String s : cur) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < 26; j++) {
if (str[i] != (char)('a' + j)) {
char temp = str[i];
str[i] = (char)('a' + j);
String candidate = new String(str);
if (candidate.equals(end))
return dist;
if (!used.contains(candidate) && dict.contains(
candidate)) {
newCur.add(candidate);
used.add(candidate);
}
str[i] = temp;
}
}
}
}
cur = newCur;
}
return 0;
}
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet
HashSet
cur.add(start);
while(!cur.isEmpty()) {
HashSet
dist++;
for (String s : cur) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < 26; j++) {
if (str[i] != (char)('a' + j)) {
char temp = str[i];
str[i] = (char)('a' + j);
String candidate = new String(str);
if (candidate.equals(end))
return dist;
if (!used.contains(candidate) && dict.contains(
candidate)) {
newCur.add(candidate);
used.add(candidate);
}
str[i] = temp;
}
}
}
}
cur = newCur;
}
return 0;
}
b*u
36 楼
从两头往中间BFS，还能快点
x*6
37 楼
牛啊，等着leetcode刷新题。。。
P*b
38 楼
"hot", "hot", ["hot","dot"]
不明白这个为什么结果是3
【在 p****e 的大作中提到】
: rt
不明白这个为什么结果是3
【在 p****e 的大作中提到】
: rt
g*9
39 楼
写了一个能过大数据test的C++版本，回馈版友了
大家见笑了。。
单纯的建立图，再暴力BFS确实过不了大数据的，平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector & v) {
v.clear();
int n = s.size();
string scopy;
char c;
int i;
for (i = 0; i < n; i++) {
scopy = s;
for (c = 'a'; c <= 'z'; c++) {
if (s[i] != c) {
scopy[i] = c;
v.push_back(scopy);
}
}
}
return;
}
int ladderLength(string start, string end, unordered_set &dict) {
int n = start.size();
if (n != end.size()) {
return 0;
}
unordered_set::iterator it;
unordered_map visited;
unordered_map::iterator mt;
for (it = dict.begin(); it != dict.end(); it++) {
visited[*it] = 0;
}
visited[start] = 1;
deque q;
q.push_back(start);
string k, c;
vector can;
int i;
while (1) {
if (q.empty()) {
return 0;
}
k = q.front();
q.pop_front();
gen(k, can);
for (i = 0; i < can.size(); i++) {
string & w = can[i];
mt = visited.find(w);
if (mt != visited.end() &&
(mt->second == 0 || w == end)) {
q.push_back(w);
mt->second = visited[k] + 1;
if (w == end) {
return mt->second;
}
}
}
} // while
return 0;
}
};
大家见笑了。。
单纯的建立图，再暴力BFS确实过不了大数据的，平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector
v.clear();
int n = s.size();
string scopy;
char c;
int i;
for (i = 0; i < n; i++) {
scopy = s;
for (c = 'a'; c <= 'z'; c++) {
if (s[i] != c) {
scopy[i] = c;
v.push_back(scopy);
}
}
}
return;
}
int ladderLength(string start, string end, unordered_set
int n = start.size();
if (n != end.size()) {
return 0;
}
unordered_set
unordered_map
unordered_map
for (it = dict.begin(); it != dict.end(); it++) {
visited[*it] = 0;
}
visited[start] = 1;
deque
q.push_back(start);
string k, c;
vector
int i;
while (1) {
if (q.empty()) {
return 0;
}
k = q.front();
q.pop_front();
gen(k, can);
for (i = 0; i < can.size(); i++) {
string & w = can[i];
mt = visited.find(w);
if (mt != visited.end() &&
(mt->second == 0 || w == end)) {
q.push_back(w);
mt->second = visited[k] + 1;
if (w == end) {
return mt->second;
}
}
}
} // while
return 0;
}
};
d*g
40 楼
第二题要过大集合还真不容易。。。
c*a
41 楼
写了个java的第一题
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
Queue queue = new LinkedList();
Set visited = new HashSet();
Hashtable path = new Hashtable();
List res = new ArrayList();
queue.add(start);
visited.add(start);
while(queue.size()>0){
String prev = queue.poll();
for(String curr: generate(prev, dict)){
if(curr.equals(end)){
res.add(end);
while(prev!=null){
res.add(0,prev);
prev = path.get(prev);
}
return res.size();
}
if(!visited.contains(curr)){
visited.add(curr);
queue.add(curr);
path.put(curr, prev);
}
}
}
return 0;
}
public Set generate(String s, HashSet dict){
Set words = new HashSet();
for(int i =0;i
char[] chs = s.toCharArray();
if(chs[i]!=j ){
chs[i] = j;
String ns = new String(chs);
if(dict.contains(ns))
words.add(ns);
}
}
}
return words;
}
}
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet
// Start typing your Java solution below
// DO NOT write main() function
Queue
Set
Hashtable
List
queue.add(start);
visited.add(start);
while(queue.size()>0){
String prev = queue.poll();
for(String curr: generate(prev, dict)){
if(curr.equals(end)){
res.add(end);
while(prev!=null){
res.add(0,prev);
prev = path.get(prev);
}
return res.size();
}
if(!visited.contains(curr)){
visited.add(curr);
queue.add(curr);
path.put(curr, prev);
}
}
}
return 0;
}
public Set
Set
for(int i =0;i
char[] chs = s.toCharArray();
if(chs[i]!=j ){
chs[i] = j;
String ns = new String(chs);
if(dict.contains(ns))
words.add(ns);
}
}
}
return words;
}
}
i*e
42 楼
word ladder II 有人过了 large tests 吗？
我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
整个程序不到50行。
基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多，所以性能上也没什么影响。
typedef unordered_multimap Map;
typedef pair PairIter;
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
Map map, map2;
queue q, q2;
q.push(start);
bool goal = false;
while (!q.empty()) {
string word = q.front();
q.pop();
for (int i = 0; i < start.length(); i++) {
string s = word;
for (char c = 'a'; c <= 'z'; c++) {
s[i] = c;
if (s == word) continue;
if (s == end) goal = true;
if (map.find(s) == map.end() && dict.find(s) != dict.end()) {
if (map2.find(s) == map2.end()) {
q2.push(s);
}
map2.insert(make_pair(s, word));
}
}
}
if (q.empty()) {
swap(q, q2);
map.insert(map2.begin(), map2.end());
map2.clear();
if (goal) return print(map, end, start);
}
}
return vector>();
}
// backtrack to reconstruct the path from start -> end.
vector> print(Map &map, string s, string start, int depth = 0
) {
if (depth > 0 && s == start) {
return vector>(1, vector(1, s));
}
vector> ret;
for (PairIter it = map.equal_range(s); it.first != it.second; ++it.first
) {
vector> temp = print(map, it.first->second, start,
depth+1);
for (int i = 0; i < temp.size(); i++) {
temp[i].push_back(s);
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
整个程序不到50行。
基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多，所以性能上也没什么影响。
typedef unordered_multimap
typedef pair
vector
string> &dict) {
Map map, map2;
queue
q.push(start);
bool goal = false;
while (!q.empty()) {
string word = q.front();
q.pop();
for (int i = 0; i < start.length(); i++) {
string s = word;
for (char c = 'a'; c <= 'z'; c++) {
s[i] = c;
if (s == word) continue;
if (s == end) goal = true;
if (map.find(s) == map.end() && dict.find(s) != dict.end()) {
if (map2.find(s) == map2.end()) {
q2.push(s);
}
map2.insert(make_pair(s, word));
}
}
}
if (q.empty()) {
swap(q, q2);
map.insert(map2.begin(), map2.end());
map2.clear();
if (goal) return print(map, end, start);
}
}
return vector
}
// backtrack to reconstruct the path from start -> end.
vector
) {
if (depth > 0 && s == start) {
return vector
}
vector
for (PairIter it = map.equal_range(s); it.first != it.second; ++it.first
) {
vector
depth+1);
for (int i = 0; i < temp.size(); i++) {
temp[i].push_back(s);
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
d*e
43 楼
贴个第一题，
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
queue q;
queue cnt;
unordered_set visited;
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < word.size(); i++) {
string copy(word);
for (char c = 'a'; c <= 'z'; c++)
if (c != word[i]) {
copy[i] = c;
if (dict.find(copy) != dict.end() &&
visited.find(copy) == visited.end()) {
q.push(copy);
cnt.push(dist+1);
visited.insert(copy);
}
}
}
}
return 0;
}
};
【在 p****e 的大作中提到】
: rt
class Solution {
public:
int ladderLength(string start, string end, unordered_set
queue
queue
unordered_set
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < word.size(); i++) {
string copy(word);
for (char c = 'a'; c <= 'z'; c++)
if (c != word[i]) {
copy[i] = c;
if (dict.find(copy) != dict.end() &&
visited.find(copy) == visited.end()) {
q.push(copy);
cnt.push(dist+1);
visited.insert(copy);
}
}
}
}
return 0;
}
};
【在 p****e 的大作中提到】
: rt
w*t
44 楼
career 150上有这个题，解法就是 BFS + hashmap存路径，算是标准的解法把。
j*g
45 楼
第二个过了Large的 轻拍
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack stk[2];
unordered_set used;
unordered_map > path;
unordered_set level;
int index=0;
stk[index%2].push(start);
used.insert(start);
vector> rtn;
while(!stk[index%2].empty()&&done!=2){
if(res == size+2)
return rtn;
string current=stk[index%2].top();
stk[index%2].pop();
int N=current.length();
for(int i=0;i
if(current[i]!=s){
string tmp = current;
tmp[i]=s;
if(dict.find(tmp)!=dict.end()||!tmp.compare(end)){
if(path.find(tmp)==path.end()){
path[tmp]=vector (1,current);
level.insert(tmp);
}else{
if(level.find(tmp)!=level.end())
path[tmp].push_back(current);
}
if(!tmp.compare(end))
done=1;
else if(used.find(tmp)==used.end()){
stk[(index+1)%2].push(tmp);
used.insert(tmp);
}
}
}
}
}
if(stk[index%2].empty()){
index=index+1;
res++;
level.clear();
if(done)
done=2;
}
}
if(done)
getpath(start, end, path, rtn, vector(0,"a"));
return rtn;
}
void getpath(string start, string end, unordered_map > &rtn, vector route){
if(!start.compare(end)&&route.size()!=0){
route.push_back(end);
reverse(route.begin(), route.end());
rtn.push_back(route);
return;
}
vector up = path[end];
route.push_back(end);
for(int i=0; i
}
}
};
class Solution {
public:
vector
set
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack
unordered_set
unordered_map
unordered_set
int index=0;
stk[index%2].push(start);
used.insert(start);
vector
while(!stk[index%2].empty()&&done!=2){
if(res == size+2)
return rtn;
string current=stk[index%2].top();
stk[index%2].pop();
int N=current.length();
for(int i=0;i
if(current[i]!=s){
string tmp = current;
tmp[i]=s;
if(dict.find(tmp)!=dict.end()||!tmp.compare(end)){
if(path.find(tmp)==path.end()){
path[tmp]=vector
level.insert(tmp);
}else{
if(level.find(tmp)!=level.end())
path[tmp].push_back(current);
}
if(!tmp.compare(end))
done=1;
else if(used.find(tmp)==used.end()){
stk[(index+1)%2].push(tmp);
used.insert(tmp);
}
}
}
}
}
if(stk[index%2].empty()){
index=index+1;
res++;
level.clear();
if(done)
done=2;
}
}
if(done)
getpath(start, end, path, rtn, vector
return rtn;
}
void getpath(string start, string end, unordered_map
if(!start.compare(end)&&route.size()!=0){
route.push_back(end);
reverse(route.begin(), route.end());
rtn.push_back(route);
return;
}
vector
route.push_back(end);
for(int i=0; i
}
}
};
c*t
46 楼
大侠。
我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
还是因为这道题求的是shortest transform, 所以能提前退出？
多谢！
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
还是因为这道题求的是shortest transform, 所以能提前退出？
多谢！
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
i*e
47 楼
Use StringBuilder when you want a mutable string.
Concatenating substrings is a very slow operation.
ie,
StringBuilder ww = new StringBuilder(str);
Then inside your loop use setCharAt() to modify the character at index j.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
: 数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
: 还是因为这道题求的是shortest transform, 所以能提前退出？
: 多谢！
Concatenating substrings is a very slow operation.
ie,
StringBuilder ww = new StringBuilder(str);
Then inside your loop use setCharAt() to modify the character at index j.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
: 数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
: 还是因为这道题求的是shortest transform, 所以能提前退出？
: 多谢！
i*e
48 楼
DFS will TLE in large tests, because it exhaust all possibilities.
BFS avoids this by finding only the shortest path.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
: 数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
: 还是因为这道题求的是shortest transform, 所以能提前退出？
: 多谢！
BFS avoids this by finding only the shortest path.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
: 数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
: 还是因为这道题求的是shortest transform, 所以能提前退出？
: 多谢！
c*t
49 楼
是的，过了。多谢多谢！
【在 i**********e 的大作中提到】
: Use StringBuilder when you want a mutable string.
: Concatenating substrings is a very slow operation.
: ie,
: StringBuilder ww = new StringBuilder(str);
: Then inside your loop use setCharAt() to modify the character at index j.
【在 i**********e 的大作中提到】
: Use StringBuilder when you want a mutable string.
: Concatenating substrings is a very slow operation.
: ie,
: StringBuilder ww = new StringBuilder(str);
: Then inside your loop use setCharAt() to modify the character at index j.
h*y
50 楼
看不懂阿。
path和res的作用感觉有问题阿。。
) {
【在 c*****a 的大作中提到】
: 写了个java的第一题
: large的时间真长
: Run Status: Accepted!
: Program Runtime: 1460 milli secs
: import java.util.Set;
: import java.util.HashSet;
: import java.util.Hashtable;
: public class Solution {
: public int ladderLength(String start, String end, HashSet dict) {
: // Start typing your Java solution below
path和res的作用感觉有问题阿。。
) {
【在 c*****a 的大作中提到】
: 写了个java的第一题
: large的时间真长
: Run Status: Accepted!
: Program Runtime: 1460 milli secs
: import java.util.Set;
: import java.util.HashSet;
: import java.util.Hashtable;
: public class Solution {
: public int ladderLength(String start, String end, HashSet
: // Start typing your Java solution below
c*a
51 楼
res是我在local ide测试时用看的.可以直接用counter就行
path是用来记录哪个词变换的
cc150有这题啊
【在 h**********y 的大作中提到】
: 看不懂阿。
: path和res的作用感觉有问题阿。。
:
: ) {
path是用来记录哪个词变换的
cc150有这题啊
【在 h**********y 的大作中提到】
: 看不懂阿。
: path和res的作用感觉有问题阿。。
:
: ) {
t*6
52 楼
第二题，求指导：
class Solution {
public:
void traverse(string& start, string& root, unordered_map& current, vector>& result) {
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector new_one(current.size());
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_back(new_one);
} else {
traverse(start, str, prev, current, result);
}
current.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 S1;
vector S2;
S1.push_back(start);
unordered_map > prev;
bool found = false;
while(!S1.empty()) {
while(!S1.empty()) {
string current = S1.back();
S1.pop_back();
for (int i = 0; i < current.length(); ++i) {
for (int j = 0; j < 26; ++j) {
if ( 'a' + j != current[i] ) {
string now = current;
now[i] = 'a' + j;
if (now == end) found = true;
if (dict.find(now) != dict.end()) {
auto iter = prev.find(now);
if (iter == prev.end()) S2.push_back(now
);
prev[now].push_back(current);
}
}
}
}
}
if (found) break;
for (string s : S2) dict.erase(s);
swap(S1, S2);
}
vector > result;
vector current(1, end);
if (found) {
traverse(start, end, prev, current, result);
}
return result;
}
};
class Solution {
public:
void traverse(string& start, string& root, unordered_map
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_back(new_one);
} else {
traverse(start, str, prev, current, result);
}
current.pop_back();
}
}
vector
set
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector
vector
S1.push_back(start);
unordered_map
bool found = false;
while(!S1.empty()) {
while(!S1.empty()) {
string current = S1.back();
S1.pop_back();
for (int i = 0; i < current.length(); ++i) {
for (int j = 0; j < 26; ++j) {
if ( 'a' + j != current[i] ) {
string now = current;
now[i] = 'a' + j;
if (now == end) found = true;
if (dict.find(now) != dict.end()) {
auto iter = prev.find(now);
if (iter == prev.end()) S2.push_back(now
);
prev[now].push_back(current);
}
}
}
}
}
if (found) break;
for (string s : S2) dict.erase(s);
swap(S1, S2);
}
vector
vector
if (found) {
traverse(start, end, prev, current, result);
}
return result;
}
};
c*t
53 楼
多谢！
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了，再求帮助！
用的是双queue解法，感觉比你和wwwyhs说的hashmap>用空间
更少，时间也应该更少，为啥又超呢？（唉，我为什么又说又）
public ArrayList> findLadders(String start, String end,
HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE;
LinkedList queue = new LinkedList();
queue.add(start);
LinkedList> pathQueue = new LinkedList
ArrayList path= new ArrayList();
path.add(start);
pathQueue.add(path);
while(!queue.isEmpty()){
String theWord = queue.poll();
char[] str = theWord.toCharArray();
curr--;
path=pathQueue.poll();
for(int j=0; j
for(int i=0; i<26; i++){
char ch = (char) ('a'+i);
if(ch!=och){
str[j]=ch;
String word = new String(str);
if(word.equals(end)) {
length=count;
ArrayList newPath = new ArrayList
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList newPath = new ArrayList
newPath.add(word);
pathQueue.add(newPath);
next++;
}
str[j]=och;
}
}
}
if(curr==0){
count++;
if(count>length) return ret;
curr=next;
next=0;
}
}
return ret;
}
【在 i**********e 的大作中提到】
: DFS will TLE in large tests, because it exhaust all possibilities.
: BFS avoids this by finding only the shortest path.
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了，再求帮助！
用的是双queue解法，感觉比你和wwwyhs说的hashmap
更少，时间也应该更少，为啥又超呢？（唉，我为什么又说又）
public ArrayList
HashSet
// Start typing your Java solution below
// DO NOT write main() function
ArrayList
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE;
LinkedList
queue.add(start);
LinkedList
ArrayList
path.add(start);
pathQueue.add(path);
while(!queue.isEmpty()){
String theWord = queue.poll();
char[] str = theWord.toCharArray();
curr--;
path=pathQueue.poll();
for(int j=0; j
for(int i=0; i<26; i++){
char ch = (char) ('a'+i);
if(ch!=och){
str[j]=ch;
String word = new String(str);
if(word.equals(end)) {
length=count;
ArrayList
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList
newPath.add(word);
pathQueue.add(newPath);
next++;
}
str[j]=och;
}
}
}
if(curr==0){
count++;
if(count>length) return ret;
curr=next;
next=0;
}
}
return ret;
}
【在 i**********e 的大作中提到】
: DFS will TLE in large tests, because it exhaust all possibilities.
: BFS avoids this by finding only the shortest path.
p*e
54 楼
发个不用'a'-'z'的方法，第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start.size() != end.size()) return 0;
if(diff1(start, end)) return 2;
vector sq, eq, ms;
for(auto it = dict.begin(); it != dict.end(); ++it)
{
string s = *it;
if(s != start && s != end)
{
if(diff1(s, start))
sq.push_back(s);
else
ms.push_back(s);
}
}
eq.push_back(end);
int sizeofsq = sq.size();
int sizeofeq = eq.size();
if(sizeofsq == 0) return 0;
int beginofsq = 0, beginofeq = 0;
int step = 0;
int sizeofmap = ms.size(), nc = -1;
while(sizeofsq>beginofsq&&sizeofeq>beginofeq&&step
{
step+=2;
for(int csq = beginofsq; csq
string s = sq[csq];
for(int ceq = beginofeq; ceq
if(diff1(s,eq[ceq]))
return step+1;
}
}
nc = sizeofmap;
sizeofmap = 0;
for(int j=0; j
string m = ms[j];
bool b1 = false;
bool b2 = false;
for(int csq = beginofsq; csq
if(diff1(m, sq[csq]))
{
b1 = true;
break;
}
}
for(int ceq = beginofeq; ceq
if(diff1(m, eq[ceq]))
{
b2 = true;
break;
}
}
if(b1&&b2)
return step+2;
else if(b1)
sq.push_back(m);
else if(b2)
eq.push_back(m);
else
{
if(j != sizeofmap)
ms[sizeofmap] = m;
++sizeofmap;
}
}
beginofsq = sizeofsq;
sizeofsq = sq.size();
beginofeq = sizeofeq;
sizeofeq = eq.size();
}
return 0;
}
};
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start.size() != end.size()) return 0;
if(diff1(start, end)) return 2;
vector
for(auto it = dict.begin(); it != dict.end(); ++it)
{
string s = *it;
if(s != start && s != end)
{
if(diff1(s, start))
sq.push_back(s);
else
ms.push_back(s);
}
}
eq.push_back(end);
int sizeofsq = sq.size();
int sizeofeq = eq.size();
if(sizeofsq == 0) return 0;
int beginofsq = 0, beginofeq = 0;
int step = 0;
int sizeofmap = ms.size(), nc = -1;
while(sizeofsq>beginofsq&&sizeofeq>beginofeq&&step
{
step+=2;
for(int csq = beginofsq; csq
string s = sq[csq];
for(int ceq = beginofeq; ceq
if(diff1(s,eq[ceq]))
return step+1;
}
}
nc = sizeofmap;
sizeofmap = 0;
for(int j=0; j
string m = ms[j];
bool b1 = false;
bool b2 = false;
for(int csq = beginofsq; csq
if(diff1(m, sq[csq]))
{
b1 = true;
break;
}
}
for(int ceq = beginofeq; ceq
if(diff1(m, eq[ceq]))
{
b2 = true;
break;
}
}
if(b1&&b2)
return step+2;
else if(b1)
sq.push_back(m);
else if(b2)
eq.push_back(m);
else
{
if(j != sizeofmap)
ms[sizeofmap] = m;
++sizeofmap;
}
}
beginofsq = sizeofsq;
sizeofsq = sq.size();
beginofeq = sizeofeq;
sizeofeq = eq.size();
}
return 0;
}
};
c*t
55 楼
我想到这个解法，可是 start to a string可以有多个路径，那hashmap>岂不是不行？需要hashmap>>?
还有一个是麻烦，而且要存所有路径很耗费mem，难道完成BFS 一个level以后，还要
remove them from hashmap?
所以后来我才改为双queue解法。
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
还有一个是麻烦，而且要存所有路径很耗费mem，难道完成BFS 一个level以后，还要
remove them from hashmap?
所以后来我才改为双queue解法。
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
c*t
56 楼
你这个能过大数据吗？
【在 p****e 的大作中提到】
: 发个不用'a'-'z'的方法，第一题
: class Solution {
: public:
: bool diff1(string &s1, string &s2)
: {
: int diff = 0;
: //if(s1.size() != s2.size()) return false;
: for(int i = 0; i < s1.size(); ++i)
: {
: if(s1[i] != s2[i])
【在 p****e 的大作中提到】
: 发个不用'a'-'z'的方法，第一题
: class Solution {
: public:
: bool diff1(string &s1, string &s2)
: {
: int diff = 0;
: //if(s1.size() != s2.size()) return false;
: for(int i = 0; i < s1.size(); ++i)
: {
: if(s1[i] != s2[i])
c*t
57 楼
你用的是dfs?
【在 j********g 的大作中提到】
: 第二个过了Large的 轻拍
: class Solution {
: public:
: vector> findLadders(string start, string end, unordered_
: set &dict) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int size=dict.size();
: int res=1;
: int done=0;
【在 j********g 的大作中提到】
: 第二个过了Large的 轻拍
: class Solution {
: public:
: vector
: set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int size=dict.size();
: int res=1;
: int done=0;
p*e
58 楼
能啊，1580ms
【在 c********t 的大作中提到】
: 你这个能过大数据吗？
【在 c********t 的大作中提到】
: 你这个能过大数据吗？
c*t
59 楼
因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
【在 p****e 的大作中提到】
: 能啊，1580ms
【在 p****e 的大作中提到】
: 能啊，1580ms
p*e
60 楼
不是每次都遍历字典，是每次循环后字典长度都会减少的
修改了一下，第二题也通过OJ large了，不过有点长，就不贴了
大）
【在 c********t 的大作中提到】
: 因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
修改了一下，第二题也通过OJ large了，不过有点长，就不贴了
大）
【在 c********t 的大作中提到】
: 因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
c*t
61 楼
看明白了.
1.遍历 构造map
2.由map, backtrack重建pathes
我模仿的写了一个java的，真的过了。1592ms
虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
多path吧(每个node都要建一个path)，读写太多了，而这个解法存的是edges(每个node
只用存parent nodes),读写少些。
【在 i**********e 的大作中提到】
: word ladder II 有人过了 large tests 吗？
: 我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
: 思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
: 整个程序不到50行。
: 基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
: 差很多。但路径组合没那么多，所以性能上也没什么影响。
: typedef unordered_multimap Map;
: typedef pair PairIter;
: vector> findLadders(string start, string end, unordered_set<
: string> &dict) {
1.遍历 构造map
2.由map, backtrack重建pathes
我模仿的写了一个java的，真的过了。1592ms
虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
多path吧(每个node都要建一个path)，读写太多了，而这个解法存的是edges(每个node
只用存parent nodes),读写少些。
【在 i**********e 的大作中提到】
: word ladder II 有人过了 large tests 吗？
: 我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
: 思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
: 整个程序不到50行。
: 基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
: 差很多。但路径组合没那么多，所以性能上也没什么影响。
: typedef unordered_multimap
: typedef pair
: vector
: string> &dict) {
c*5
62 楼
Could you post your java version code? Thanks a lot.
node
【在 c********t 的大作中提到】
: 看明白了.
: 1.遍历 构造map
: 2.由map, backtrack重建pathes
: 我模仿的写了一个java的，真的过了。1592ms
: 虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
: 多path吧(每个node都要建一个path)，读写太多了，而这个解法存的是edges(每个node
: 只用存parent nodes),读写少些。
node
【在 c********t 的大作中提到】
: 看明白了.
: 1.遍历 构造map
: 2.由map, backtrack重建pathes
: 我模仿的写了一个java的，真的过了。1592ms
: 虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
: 多path吧(每个node都要建一个path)，读写太多了，而这个解法存的是edges(每个node
: 只用存parent nodes),读写少些。
f*t
63 楼
相当丑陋的BFS，已经尽量去除copy string的时间了，但还是超时，求指点T_T
class Path {
public:
Path() { path = new vector; }
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector(*path);
return np;
}
vector *path;
};
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
vector> ans;
queue q;
Path *np = new Path;
np->path->push_back(&start);
q.push(np);
unordered_set used;
queue levelUsed;
while (!q.empty()) {
int n = q.size();
while (n-- > 0) {
Path *p = q.front();
string temp(*p->path->back());
for (int i = 0; i < temp.size(); i++) {
char tc = temp[i];
for (int j = 0; j < 26; j++) {
if (tc == (char)('a' + j))
continue;
temp[i] = (char)('a' + j);
unordered_set::iterator it = dict.find(temp);
if (it != dict.end() && used.find(&(*it)) == used.
end()) {
np = p->duplicate();
np->path->push_back(&(*it));
if (temp == end) {
vector line;
for (vector::iterator itv =
np->path->begin(); itv != np->path->end(); itv++)
line.push_back(**itv);
ans.push_back(line);
}
q.push(np);
levelUsed.push(&(*it));
}
}
temp[i] = tc;
}
q.pop();
delete p;
}
if (!ans.empty())
break;
while(!levelUsed.empty()) {
used.insert(levelUsed.front());
levelUsed.pop();
}
}
return ans;
}
};
class Path {
public:
Path() { path = new vector
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector
return np;
}
vector
};
class Solution {
public:
vector
set
vector
queue
Path *np = new Path;
np->path->push_back(&start);
q.push(np);
unordered_set
queue
while (!q.empty()) {
int n = q.size();
while (n-- > 0) {
Path *p = q.front();
string temp(*p->path->back());
for (int i = 0; i < temp.size(); i++) {
char tc = temp[i];
for (int j = 0; j < 26; j++) {
if (tc == (char)('a' + j))
continue;
temp[i] = (char)('a' + j);
unordered_set
if (it != dict.end() && used.find(&(*it)) == used.
end()) {
np = p->duplicate();
np->path->push_back(&(*it));
if (temp == end) {
vector
for (vector
np->path->begin(); itv != np->path->end(); itv++)
line.push_back(**itv);
ans.push_back(line);
}
q.push(np);
levelUsed.push(&(*it));
}
}
temp[i] = tc;
}
q.pop();
delete p;
}
if (!ans.empty())
break;
while(!levelUsed.empty()) {
used.insert(levelUsed.front());
levelUsed.pop();
}
}
return ans;
}
};
i*e
64 楼
我测试了你的程序，差不多4秒跑完所有test。
简单优化了一下变成3.5秒，还差1.5秒。
说说你duplicate 路径的时候怎么做的？
有把之前共享的路径也copy 下来了吗？
【在 f*******t 的大作中提到】
: 相当丑陋的BFS，已经尽量去除copy string的时间了，但还是超时，求指点T_T
: class Path {
: public:
: Path() { path = new vector; }
:
: ~Path() { delete path; }
:
: Path* duplicate() const {
: Path *np = new Path;
: np->path = new vector(*path);
简单优化了一下变成3.5秒，还差1.5秒。
说说你duplicate 路径的时候怎么做的？
有把之前共享的路径也copy 下来了吗？
【在 f*******t 的大作中提到】
: 相当丑陋的BFS，已经尽量去除copy string的时间了，但还是超时，求指点T_T
: class Path {
: public:
: Path() { path = new vector
:
: ~Path() { delete path; }
:
: Path* duplicate() const {
: Path *np = new Path;
: np->path = new vector
f*t
65 楼
是的，这样即使只存指针也会超时呀。准备今天写下存edge的解法
【在 i**********e 的大作中提到】
: 我测试了你的程序，差不多4秒跑完所有test。
: 简单优化了一下变成3.5秒，还差1.5秒。
: 说说你duplicate 路径的时候怎么做的？
: 有把之前共享的路径也copy 下来了吗？
【在 i**********e 的大作中提到】
: 我测试了你的程序，差不多4秒跑完所有test。
: 简单优化了一下变成3.5秒，还差1.5秒。
: 说说你duplicate 路径的时候怎么做的？
: 有把之前共享的路径也copy 下来了吗？
y*e
66 楼
DFS+pruning?
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题，求指导：
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map& current, vector>& result) {
: auto iter = prev.find(root);
: for (string str : iter->second) {
: current.push_back(str);
: if (str == start) {
: vector new_one(current.size());
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题，求指导：
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map
: auto iter = prev.find(root);
: for (string str : iter->second) {
: current.push_back(str);
: if (str == start) {
: vector
p*2
67 楼
1337你这规则从哪里来的？我怎么感觉不对呀。
【在 i**********e 的大作中提到】
: 是比较奇怪，但仔细看好规则：
: Each intermediate word must exist in the dictionary
: start 和 end 都不是 intermediate word，所以字典可有可无。
:
: ) {
p*e
68 楼
rt
w*x
69 楼
这题怎么那么别扭，原来目标单词不在字典里...
还有我咋超时了...
还有我咋超时了...
i*e
70 楼
贴贴你代码？
w*x
71 楼
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
unordered_set visited;
visited.insert(start);
queue que;
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set::iterator it = dict.begin();
it != dict.end(); it++)
{
if (visited.find(*it) == visited.end() && canChng(*it,
strCur))
{
que.push(*it);
visited.insert(*it);
nNextNum++;
}
}
if (canChng(end, strCur))
return nCurLev+1;
if (nCurNum <= 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return 0;
}
bool canChng(string a, string b)
{
if (a.length() != b.length())
return false;
bool bDiff = false;
for (int i = 0; i < a.length(); i++)
{
if (a.at(i) != b.at(i))
{
if (bDiff)
return false;
bDiff = true;
}
}
return bDiff;
}
};
public:
int ladderLength(string start, string end, unordered_set
unordered_set
visited.insert(start);
queue
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set
it != dict.end(); it++)
{
if (visited.find(*it) == visited.end() && canChng(*it,
strCur))
{
que.push(*it);
visited.insert(*it);
nNextNum++;
}
}
if (canChng(end, strCur))
return nCurLev+1;
if (nCurNum <= 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return 0;
}
bool canChng(string a, string b)
{
if (a.length() != b.length())
return false;
bool bDiff = false;
for (int i = 0; i < a.length(); i++)
{
if (a.at(i) != b.at(i))
{
if (bDiff)
return false;
bDiff = true;
}
}
return bDiff;
}
};
i*e
72 楼
如果字典很大怎么办？
p*p
73 楼
large TLE了
不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list queue;
set visited;
map stepMap;
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string s = queue.front();
queue.pop_front();
if (diffByOne(s, end)) return stepMap[s] + 1;
int currentStep = stepMap[s];
for (string strInDict : dict) {
if (visited.find(strInDict) != visited.end()) continue;
if (diffByOne(s, strInDict)) {
queue.push_back(strInDict);
visited.insert(strInDict);
stepMap[strInDict] = currentStep + 1;
}
}
}
return 0;
}
bool diffByOne(string &s1, string &s2) {
if (s1.size() != s2.size()) return false;
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++diff;
if (diff > 1) return false;
}
return diff == 1 ? true : false;
}
};
不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
list
set
map
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string s = queue.front();
queue.pop_front();
if (diffByOne(s, end)) return stepMap[s] + 1;
int currentStep = stepMap[s];
for (string strInDict : dict) {
if (visited.find(strInDict) != visited.end()) continue;
if (diffByOne(s, strInDict)) {
queue.push_back(strInDict);
visited.insert(strInDict);
stepMap[strInDict] = currentStep + 1;
}
}
}
return 0;
}
bool diffByOne(string &s1, string &s2) {
if (s1.size() != s2.size()) return false;
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++diff;
if (diff > 1) return false;
}
return diff == 1 ? true : false;
}
};
i*e
74 楼
关于怎么测下一步是不是合法：
每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
了。
每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
了。
a*o
75 楼
我来贴个能过的,比较丑,大家见谅...
int ladderLength(string start, string end, tr1::unordered_set &dict)
{
set contain;
int count = 1;
queue list[2];
list[0].push(start);
while (list[0].size()!= 0 || list[1].size()!=0){
int oldlist = 0;
int newlist = 1;
if (list[0].size()== 0){
oldlist = 1;
newlist = 0;
}
while (list[oldlist].size() != 0){
string curr = list[oldlist].front();
list[oldlist].pop();
if (contain.count(curr) > 0) continue;
contain.insert(curr);
for (int i = 0; i< curr.size(); i++){
for (int j = 0; j<26; j++){
char temp = curr[i];
char newtemp = (char) ('a'+j);
if (temp != newtemp){
string newcurr = curr;
newcurr[i] = newtemp;
if (newcurr == end) return count
+1;
if (dict.count(newcurr)> 0){
list[newlist].push(
newcurr);
}
}
}
}
}
count ++;
}
return 0;
}
【在 p****e 的大作中提到】
: rt
int ladderLength(string start, string end, tr1::unordered_set
{
set
int count = 1;
queue
list[0].push(start);
while (list[0].size()!= 0 || list[1].size()!=0){
int oldlist = 0;
int newlist = 1;
if (list[0].size()== 0){
oldlist = 1;
newlist = 0;
}
while (list[oldlist].size() != 0){
string curr = list[oldlist].front();
list[oldlist].pop();
if (contain.count(curr) > 0) continue;
contain.insert(curr);
for (int i = 0; i< curr.size(); i++){
for (int j = 0; j<26; j++){
char temp = curr[i];
char newtemp = (char) ('a'+j);
if (temp != newtemp){
string newcurr = curr;
newcurr[i] = newtemp;
if (newcurr == end) return count
+1;
if (dict.count(newcurr)> 0){
list[newlist].push(
newcurr);
}
}
}
}
}
count ++;
}
return 0;
}
【在 p****e 的大作中提到】
: rt
w*x
76 楼
) {
这个也超时了
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list
: set
: map
i*e
77 楼
是比较奇怪，但仔细看好规则：
Each intermediate word must exist in the dictionary
start 和 end 都不是 intermediate word，所以字典可有可无。
) {
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set &dict) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list queue;
: set visited;
: map stepMap;
Each intermediate word must exist in the dictionary
start 和 end 都不是 intermediate word，所以字典可有可无。
) {
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list
: set
: map
w*x
78 楼
没看明白..
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
a*o
79 楼
就是先变再到查词典查 VS. 先从词典抓一个再查是不是只变了一个字母
【在 w****x 的大作中提到】
:
: 没看明白..
【在 w****x 的大作中提到】
:
: 没看明白..
i*e
80 楼
你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
【在 w****x 的大作中提到】
:
: 没看明白..
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
【在 w****x 的大作中提到】
:
: 没看明白..
w*x
81 楼
这个啊，没意思，太tricky了
【在 a***o 的大作中提到】
: 就是先变再到查词典查 VS. 先从词典抓一个再查是不是只变了一个字母
a*o
82 楼
leetcode大侠,能不能指点一下这个ladder2怎么做啊
DFS能过么?还是要BFS+记路径?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
DFS能过么?还是要BFS+记路径?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
w*x
83 楼
感觉正常的思路是有一步pre processing,就是先把dict建图，
然后后续的查询ladder从建好的图为出发点。
这个图可以用map表示
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
w*x
84 楼
用map
wordladder2 太麻烦了，不做了,string的hash map还得自己写
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
a*o
85 楼
是啊,搞了个递归超时了,
看来得上bfs+map,不知道会不会超mem
【在 w****x 的大作中提到】
:
: 用map>记录路径，然后递归输出吧
: wordladder2 太麻烦了，不做了,string的hash map还得自己写
看来得上bfs+map,不知道会不会超mem
【在 w****x 的大作中提到】
:
: 用map
: wordladder2 太麻烦了，不做了,string的hash map还得自己写
i*e
86 楼
DFS 肯定过不了。最长的ladder length 是 42。
BFS + 记路径是正解。
但怎么记路径使得空间少 + 重建路径是比较tricky。
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
BFS + 记路径是正解。
但怎么记路径使得空间少 + 重建路径是比较tricky。
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
a*o
87 楼
多谢,再去琢磨琢磨
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
w*x
88 楼
BFS然后构建map
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
i*e
89 楼
牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
start。其实输出
路径不用递归也可以，比较麻烦一些就是了。
【在 w****x 的大作中提到】
:
: BFS然后构建map>结构，输出路径还是得递归吧
start。其实输出
路径不用递归也可以，比较麻烦一些就是了。
【在 w****x 的大作中提到】
:
: BFS然后构建map
w*x
90 楼
你饶了我吧。。。
是不是有个unordered_map可以hash string??
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
i*e
91 楼
你要的是 unordered_multimap 吧。
一个 key 可以 map 到好几个 value.
一个 key 可以 map 到好几个 value.
p*p
92 楼
原来是这样
这题在CC上有，但是没仔细看过，现在回头看原来是这么回事，学习了
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
这题在CC上有，但是没仔细看过，现在回头看原来是这么回事，学习了
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
f*t
93 楼
public int ladderLength(String start, String end, HashSet dict) {
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet used = new HashSet();
HashSet cur = new HashSet();
cur.add(start);
while(!cur.isEmpty()) {
HashSet newCur = new HashSet();
dist++;
for (String s : cur) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < 26; j++) {
if (str[i] != (char)('a' + j)) {
char temp = str[i];
str[i] = (char)('a' + j);
String candidate = new String(str);
if (candidate.equals(end))
return dist;
if (!used.contains(candidate) && dict.contains(
candidate)) {
newCur.add(candidate);
used.add(candidate);
}
str[i] = temp;
}
}
}
}
cur = newCur;
}
return 0;
}
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet
HashSet
cur.add(start);
while(!cur.isEmpty()) {
HashSet
dist++;
for (String s : cur) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < 26; j++) {
if (str[i] != (char)('a' + j)) {
char temp = str[i];
str[i] = (char)('a' + j);
String candidate = new String(str);
if (candidate.equals(end))
return dist;
if (!used.contains(candidate) && dict.contains(
candidate)) {
newCur.add(candidate);
used.add(candidate);
}
str[i] = temp;
}
}
}
}
cur = newCur;
}
return 0;
}
b*u
94 楼
从两头往中间BFS，还能快点
x*6
95 楼
牛啊，等着leetcode刷新题。。。
P*b
96 楼
"hot", "hot", ["hot","dot"]
不明白这个为什么结果是3
【在 p****e 的大作中提到】
: rt
不明白这个为什么结果是3
【在 p****e 的大作中提到】
: rt
g*9
97 楼
写了一个能过大数据test的C++版本，回馈版友了
大家见笑了。。
单纯的建立图，再暴力BFS确实过不了大数据的，平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector & v) {
v.clear();
int n = s.size();
string scopy;
char c;
int i;
for (i = 0; i < n; i++) {
scopy = s;
for (c = 'a'; c <= 'z'; c++) {
if (s[i] != c) {
scopy[i] = c;
v.push_back(scopy);
}
}
}
return;
}
int ladderLength(string start, string end, unordered_set &dict) {
int n = start.size();
if (n != end.size()) {
return 0;
}
unordered_set::iterator it;
unordered_map visited;
unordered_map::iterator mt;
for (it = dict.begin(); it != dict.end(); it++) {
visited[*it] = 0;
}
visited[start] = 1;
deque q;
q.push_back(start);
string k, c;
vector can;
int i;
while (1) {
if (q.empty()) {
return 0;
}
k = q.front();
q.pop_front();
gen(k, can);
for (i = 0; i < can.size(); i++) {
string & w = can[i];
mt = visited.find(w);
if (mt != visited.end() &&
(mt->second == 0 || w == end)) {
q.push_back(w);
mt->second = visited[k] + 1;
if (w == end) {
return mt->second;
}
}
}
} // while
return 0;
}
};
大家见笑了。。
单纯的建立图，再暴力BFS确实过不了大数据的，平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector
v.clear();
int n = s.size();
string scopy;
char c;
int i;
for (i = 0; i < n; i++) {
scopy = s;
for (c = 'a'; c <= 'z'; c++) {
if (s[i] != c) {
scopy[i] = c;
v.push_back(scopy);
}
}
}
return;
}
int ladderLength(string start, string end, unordered_set
int n = start.size();
if (n != end.size()) {
return 0;
}
unordered_set
unordered_map
unordered_map
for (it = dict.begin(); it != dict.end(); it++) {
visited[*it] = 0;
}
visited[start] = 1;
deque
q.push_back(start);
string k, c;
vector
int i;
while (1) {
if (q.empty()) {
return 0;
}
k = q.front();
q.pop_front();
gen(k, can);
for (i = 0; i < can.size(); i++) {
string & w = can[i];
mt = visited.find(w);
if (mt != visited.end() &&
(mt->second == 0 || w == end)) {
q.push_back(w);
mt->second = visited[k] + 1;
if (w == end) {
return mt->second;
}
}
}
} // while
return 0;
}
};
d*g
98 楼
第二题要过大集合还真不容易。。。
c*a
99 楼
写了个java的第一题
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
Queue queue = new LinkedList();
Set visited = new HashSet();
Hashtable path = new Hashtable();
List res = new ArrayList();
queue.add(start);
visited.add(start);
while(queue.size()>0){
String prev = queue.poll();
for(String curr: generate(prev, dict)){
if(curr.equals(end)){
res.add(end);
while(prev!=null){
res.add(0,prev);
prev = path.get(prev);
}
return res.size();
}
if(!visited.contains(curr)){
visited.add(curr);
queue.add(curr);
path.put(curr, prev);
}
}
}
return 0;
}
public Set generate(String s, HashSet dict){
Set words = new HashSet();
for(int i =0;i
char[] chs = s.toCharArray();
if(chs[i]!=j ){
chs[i] = j;
String ns = new String(chs);
if(dict.contains(ns))
words.add(ns);
}
}
}
return words;
}
}
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet
// Start typing your Java solution below
// DO NOT write main() function
Queue
Set
Hashtable
List
queue.add(start);
visited.add(start);
while(queue.size()>0){
String prev = queue.poll();
for(String curr: generate(prev, dict)){
if(curr.equals(end)){
res.add(end);
while(prev!=null){
res.add(0,prev);
prev = path.get(prev);
}
return res.size();
}
if(!visited.contains(curr)){
visited.add(curr);
queue.add(curr);
path.put(curr, prev);
}
}
}
return 0;
}
public Set
Set
for(int i =0;i
char[] chs = s.toCharArray();
if(chs[i]!=j ){
chs[i] = j;
String ns = new String(chs);
if(dict.contains(ns))
words.add(ns);
}
}
}
return words;
}
}
i*e
100 楼
word ladder II 有人过了 large tests 吗？
我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
整个程序不到50行。
基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多，所以性能上也没什么影响。
typedef unordered_multimap Map;
typedef pair PairIter;
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
Map map, map2;
queue q, q2;
q.push(start);
bool goal = false;
while (!q.empty()) {
string word = q.front();
q.pop();
for (int i = 0; i < start.length(); i++) {
string s = word;
for (char c = 'a'; c <= 'z'; c++) {
s[i] = c;
if (s == word) continue;
if (s == end) goal = true;
if (map.find(s) == map.end() && dict.find(s) != dict.end()) {
if (map2.find(s) == map2.end()) {
q2.push(s);
}
map2.insert(make_pair(s, word));
}
}
}
if (q.empty()) {
swap(q, q2);
map.insert(map2.begin(), map2.end());
map2.clear();
if (goal) return print(map, end, start);
}
}
return vector>();
}
// backtrack to reconstruct the path from start -> end.
vector> print(Map &map, string s, string start, int depth = 0
) {
if (depth > 0 && s == start) {
return vector>(1, vector(1, s));
}
vector> ret;
for (PairIter it = map.equal_range(s); it.first != it.second; ++it.first
) {
vector> temp = print(map, it.first->second, start,
depth+1);
for (int i = 0; i < temp.size(); i++) {
temp[i].push_back(s);
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
整个程序不到50行。
基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多，所以性能上也没什么影响。
typedef unordered_multimap
typedef pair
vector
string> &dict) {
Map map, map2;
queue
q.push(start);
bool goal = false;
while (!q.empty()) {
string word = q.front();
q.pop();
for (int i = 0; i < start.length(); i++) {
string s = word;
for (char c = 'a'; c <= 'z'; c++) {
s[i] = c;
if (s == word) continue;
if (s == end) goal = true;
if (map.find(s) == map.end() && dict.find(s) != dict.end()) {
if (map2.find(s) == map2.end()) {
q2.push(s);
}
map2.insert(make_pair(s, word));
}
}
}
if (q.empty()) {
swap(q, q2);
map.insert(map2.begin(), map2.end());
map2.clear();
if (goal) return print(map, end, start);
}
}
return vector
}
// backtrack to reconstruct the path from start -> end.
vector
) {
if (depth > 0 && s == start) {
return vector
}
vector
for (PairIter it = map.equal_range(s); it.first != it.second; ++it.first
) {
vector
depth+1);
for (int i = 0; i < temp.size(); i++) {
temp[i].push_back(s);
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
d*e
101 楼
贴个第一题，
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
queue q;
queue cnt;
unordered_set visited;
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < word.size(); i++) {
string copy(word);
for (char c = 'a'; c <= 'z'; c++)
if (c != word[i]) {
copy[i] = c;
if (dict.find(copy) != dict.end() &&
visited.find(copy) == visited.end()) {
q.push(copy);
cnt.push(dist+1);
visited.insert(copy);
}
}
}
}
return 0;
}
};
【在 p****e 的大作中提到】
: rt
class Solution {
public:
int ladderLength(string start, string end, unordered_set
queue
queue
unordered_set
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < word.size(); i++) {
string copy(word);
for (char c = 'a'; c <= 'z'; c++)
if (c != word[i]) {
copy[i] = c;
if (dict.find(copy) != dict.end() &&
visited.find(copy) == visited.end()) {
q.push(copy);
cnt.push(dist+1);
visited.insert(copy);
}
}
}
}
return 0;
}
};
【在 p****e 的大作中提到】
: rt
w*t
102 楼
career 150上有这个题，解法就是 BFS + hashmap存路径，算是标准的解法把。
j*g
103 楼
第二个过了Large的 轻拍
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack stk[2];
unordered_set used;
unordered_map > path;
unordered_set level;
int index=0;
stk[index%2].push(start);
used.insert(start);
vector> rtn;
while(!stk[index%2].empty()&&done!=2){
if(res == size+2)
return rtn;
string current=stk[index%2].top();
stk[index%2].pop();
int N=current.length();
for(int i=0;i
if(current[i]!=s){
string tmp = current;
tmp[i]=s;
if(dict.find(tmp)!=dict.end()||!tmp.compare(end)){
if(path.find(tmp)==path.end()){
path[tmp]=vector (1,current);
level.insert(tmp);
}else{
if(level.find(tmp)!=level.end())
path[tmp].push_back(current);
}
if(!tmp.compare(end))
done=1;
else if(used.find(tmp)==used.end()){
stk[(index+1)%2].push(tmp);
used.insert(tmp);
}
}
}
}
}
if(stk[index%2].empty()){
index=index+1;
res++;
level.clear();
if(done)
done=2;
}
}
if(done)
getpath(start, end, path, rtn, vector(0,"a"));
return rtn;
}
void getpath(string start, string end, unordered_map > &rtn, vector route){
if(!start.compare(end)&&route.size()!=0){
route.push_back(end);
reverse(route.begin(), route.end());
rtn.push_back(route);
return;
}
vector up = path[end];
route.push_back(end);
for(int i=0; i
}
}
};
class Solution {
public:
vector
set
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack
unordered_set
unordered_map
unordered_set
int index=0;
stk[index%2].push(start);
used.insert(start);
vector
while(!stk[index%2].empty()&&done!=2){
if(res == size+2)
return rtn;
string current=stk[index%2].top();
stk[index%2].pop();
int N=current.length();
for(int i=0;i
if(current[i]!=s){
string tmp = current;
tmp[i]=s;
if(dict.find(tmp)!=dict.end()||!tmp.compare(end)){
if(path.find(tmp)==path.end()){
path[tmp]=vector
level.insert(tmp);
}else{
if(level.find(tmp)!=level.end())
path[tmp].push_back(current);
}
if(!tmp.compare(end))
done=1;
else if(used.find(tmp)==used.end()){
stk[(index+1)%2].push(tmp);
used.insert(tmp);
}
}
}
}
}
if(stk[index%2].empty()){
index=index+1;
res++;
level.clear();
if(done)
done=2;
}
}
if(done)
getpath(start, end, path, rtn, vector
return rtn;
}
void getpath(string start, string end, unordered_map
if(!start.compare(end)&&route.size()!=0){
route.push_back(end);
reverse(route.begin(), route.end());
rtn.push_back(route);
return;
}
vector
route.push_back(end);
for(int i=0; i
}
}
};
c*t
104 楼
大侠。
我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
还是因为这道题求的是shortest transform, 所以能提前退出？
多谢！
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
还是因为这道题求的是shortest transform, 所以能提前退出？
多谢！
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
i*e
105 楼
Use StringBuilder when you want a mutable string.
Concatenating substrings is a very slow operation.
ie,
StringBuilder ww = new StringBuilder(str);
Then inside your loop use setCharAt() to modify the character at index j.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
: 数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
: 还是因为这道题求的是shortest transform, 所以能提前退出？
: 多谢！
Concatenating substrings is a very slow operation.
ie,
StringBuilder ww = new StringBuilder(str);
Then inside your loop use setCharAt() to modify the character at index j.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
: 数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
: 还是因为这道题求的是shortest transform, 所以能提前退出？
: 多谢！
i*e
106 楼
DFS will TLE in large tests, because it exhaust all possibilities.
BFS avoids this by finding only the shortest path.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
: 数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
: 还是因为这道题求的是shortest transform, 所以能提前退出？
: 多谢！
BFS avoids this by finding only the shortest path.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题，用的是一贯的DFS+recursion, 是你说的26*length的作法，结果大
: 数据超时了。这类型的题（比如word search)，我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯？还有说BFS比DFS快，是general指所有这类型的题，
: 还是因为这道题求的是shortest transform, 所以能提前退出？
: 多谢！
c*t
107 楼
是的，过了。多谢多谢！
【在 i**********e 的大作中提到】
: Use StringBuilder when you want a mutable string.
: Concatenating substrings is a very slow operation.
: ie,
: StringBuilder ww = new StringBuilder(str);
: Then inside your loop use setCharAt() to modify the character at index j.
【在 i**********e 的大作中提到】
: Use StringBuilder when you want a mutable string.
: Concatenating substrings is a very slow operation.
: ie,
: StringBuilder ww = new StringBuilder(str);
: Then inside your loop use setCharAt() to modify the character at index j.
h*y
108 楼
看不懂阿。
path和res的作用感觉有问题阿。。
) {
【在 c*****a 的大作中提到】
: 写了个java的第一题
: large的时间真长
: Run Status: Accepted!
: Program Runtime: 1460 milli secs
: import java.util.Set;
: import java.util.HashSet;
: import java.util.Hashtable;
: public class Solution {
: public int ladderLength(String start, String end, HashSet dict) {
: // Start typing your Java solution below
path和res的作用感觉有问题阿。。
) {
【在 c*****a 的大作中提到】
: 写了个java的第一题
: large的时间真长
: Run Status: Accepted!
: Program Runtime: 1460 milli secs
: import java.util.Set;
: import java.util.HashSet;
: import java.util.Hashtable;
: public class Solution {
: public int ladderLength(String start, String end, HashSet
: // Start typing your Java solution below
c*a
109 楼
res是我在local ide测试时用看的.可以直接用counter就行
path是用来记录哪个词变换的
cc150有这题啊
【在 h**********y 的大作中提到】
: 看不懂阿。
: path和res的作用感觉有问题阿。。
:
: ) {
path是用来记录哪个词变换的
cc150有这题啊
【在 h**********y 的大作中提到】
: 看不懂阿。
: path和res的作用感觉有问题阿。。
:
: ) {
t*6
110 楼
第二题，求指导：
class Solution {
public:
void traverse(string& start, string& root, unordered_map& current, vector>& result) {
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector new_one(current.size());
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_back(new_one);
} else {
traverse(start, str, prev, current, result);
}
current.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 S1;
vector S2;
S1.push_back(start);
unordered_map > prev;
bool found = false;
while(!S1.empty()) {
while(!S1.empty()) {
string current = S1.back();
S1.pop_back();
for (int i = 0; i < current.length(); ++i) {
for (int j = 0; j < 26; ++j) {
if ( 'a' + j != current[i] ) {
string now = current;
now[i] = 'a' + j;
if (now == end) found = true;
if (dict.find(now) != dict.end()) {
auto iter = prev.find(now);
if (iter == prev.end()) S2.push_back(now
);
prev[now].push_back(current);
}
}
}
}
}
if (found) break;
for (string s : S2) dict.erase(s);
swap(S1, S2);
}
vector > result;
vector current(1, end);
if (found) {
traverse(start, end, prev, current, result);
}
return result;
}
};
class Solution {
public:
void traverse(string& start, string& root, unordered_map
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_back(new_one);
} else {
traverse(start, str, prev, current, result);
}
current.pop_back();
}
}
vector
set
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector
vector
S1.push_back(start);
unordered_map
bool found = false;
while(!S1.empty()) {
while(!S1.empty()) {
string current = S1.back();
S1.pop_back();
for (int i = 0; i < current.length(); ++i) {
for (int j = 0; j < 26; ++j) {
if ( 'a' + j != current[i] ) {
string now = current;
now[i] = 'a' + j;
if (now == end) found = true;
if (dict.find(now) != dict.end()) {
auto iter = prev.find(now);
if (iter == prev.end()) S2.push_back(now
);
prev[now].push_back(current);
}
}
}
}
}
if (found) break;
for (string s : S2) dict.erase(s);
swap(S1, S2);
}
vector
vector
if (found) {
traverse(start, end, prev, current, result);
}
return result;
}
};
c*t
111 楼
多谢！
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了，再求帮助！
用的是双queue解法，感觉比你和wwwyhs说的hashmap>用空间
更少，时间也应该更少，为啥又超呢？（唉，我为什么又说又）
public ArrayList> findLadders(String start, String end,
HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE;
LinkedList queue = new LinkedList();
queue.add(start);
LinkedList> pathQueue = new LinkedList
ArrayList path= new ArrayList();
path.add(start);
pathQueue.add(path);
while(!queue.isEmpty()){
String theWord = queue.poll();
char[] str = theWord.toCharArray();
curr--;
path=pathQueue.poll();
for(int j=0; j
for(int i=0; i<26; i++){
char ch = (char) ('a'+i);
if(ch!=och){
str[j]=ch;
String word = new String(str);
if(word.equals(end)) {
length=count;
ArrayList newPath = new ArrayList
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList newPath = new ArrayList
newPath.add(word);
pathQueue.add(newPath);
next++;
}
str[j]=och;
}
}
}
if(curr==0){
count++;
if(count>length) return ret;
curr=next;
next=0;
}
}
return ret;
}
【在 i**********e 的大作中提到】
: DFS will TLE in large tests, because it exhaust all possibilities.
: BFS avoids this by finding only the shortest path.
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了，再求帮助！
用的是双queue解法，感觉比你和wwwyhs说的hashmap
更少，时间也应该更少，为啥又超呢？（唉，我为什么又说又）
public ArrayList
HashSet
// Start typing your Java solution below
// DO NOT write main() function
ArrayList
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE;
LinkedList
queue.add(start);
LinkedList
ArrayList
path.add(start);
pathQueue.add(path);
while(!queue.isEmpty()){
String theWord = queue.poll();
char[] str = theWord.toCharArray();
curr--;
path=pathQueue.poll();
for(int j=0; j
for(int i=0; i<26; i++){
char ch = (char) ('a'+i);
if(ch!=och){
str[j]=ch;
String word = new String(str);
if(word.equals(end)) {
length=count;
ArrayList
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList
newPath.add(word);
pathQueue.add(newPath);
next++;
}
str[j]=och;
}
}
}
if(curr==0){
count++;
if(count>length) return ret;
curr=next;
next=0;
}
}
return ret;
}
【在 i**********e 的大作中提到】
: DFS will TLE in large tests, because it exhaust all possibilities.
: BFS avoids this by finding only the shortest path.
p*e
112 楼
发个不用'a'-'z'的方法，第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start.size() != end.size()) return 0;
if(diff1(start, end)) return 2;
vector sq, eq, ms;
for(auto it = dict.begin(); it != dict.end(); ++it)
{
string s = *it;
if(s != start && s != end)
{
if(diff1(s, start))
sq.push_back(s);
else
ms.push_back(s);
}
}
eq.push_back(end);
int sizeofsq = sq.size();
int sizeofeq = eq.size();
if(sizeofsq == 0) return 0;
int beginofsq = 0, beginofeq = 0;
int step = 0;
int sizeofmap = ms.size(), nc = -1;
while(sizeofsq>beginofsq&&sizeofeq>beginofeq&&step
{
step+=2;
for(int csq = beginofsq; csq
string s = sq[csq];
for(int ceq = beginofeq; ceq
if(diff1(s,eq[ceq]))
return step+1;
}
}
nc = sizeofmap;
sizeofmap = 0;
for(int j=0; j
string m = ms[j];
bool b1 = false;
bool b2 = false;
for(int csq = beginofsq; csq
if(diff1(m, sq[csq]))
{
b1 = true;
break;
}
}
for(int ceq = beginofeq; ceq
if(diff1(m, eq[ceq]))
{
b2 = true;
break;
}
}
if(b1&&b2)
return step+2;
else if(b1)
sq.push_back(m);
else if(b2)
eq.push_back(m);
else
{
if(j != sizeofmap)
ms[sizeofmap] = m;
++sizeofmap;
}
}
beginofsq = sizeofsq;
sizeofsq = sq.size();
beginofeq = sizeofeq;
sizeofeq = eq.size();
}
return 0;
}
};
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start.size() != end.size()) return 0;
if(diff1(start, end)) return 2;
vector
for(auto it = dict.begin(); it != dict.end(); ++it)
{
string s = *it;
if(s != start && s != end)
{
if(diff1(s, start))
sq.push_back(s);
else
ms.push_back(s);
}
}
eq.push_back(end);
int sizeofsq = sq.size();
int sizeofeq = eq.size();
if(sizeofsq == 0) return 0;
int beginofsq = 0, beginofeq = 0;
int step = 0;
int sizeofmap = ms.size(), nc = -1;
while(sizeofsq>beginofsq&&sizeofeq>beginofeq&&step
{
step+=2;
for(int csq = beginofsq; csq
string s = sq[csq];
for(int ceq = beginofeq; ceq
if(diff1(s,eq[ceq]))
return step+1;
}
}
nc = sizeofmap;
sizeofmap = 0;
for(int j=0; j
string m = ms[j];
bool b1 = false;
bool b2 = false;
for(int csq = beginofsq; csq
if(diff1(m, sq[csq]))
{
b1 = true;
break;
}
}
for(int ceq = beginofeq; ceq
if(diff1(m, eq[ceq]))
{
b2 = true;
break;
}
}
if(b1&&b2)
return step+2;
else if(b1)
sq.push_back(m);
else if(b2)
eq.push_back(m);
else
{
if(j != sizeofmap)
ms[sizeofmap] = m;
++sizeofmap;
}
}
beginofsq = sizeofsq;
sizeofsq = sq.size();
beginofeq = sizeofeq;
sizeofeq = eq.size();
}
return 0;
}
};
c*t
113 楼
我想到这个解法，可是 start to a string可以有多个路径，那hashmap>岂不是不行？需要hashmap>>?
还有一个是麻烦，而且要存所有路径很耗费mem，难道完成BFS 一个level以后，还要
remove them from hashmap?
所以后来我才改为双queue解法。
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
还有一个是麻烦，而且要存所有路径很耗费mem，难道完成BFS 一个level以后，还要
remove them from hashmap?
所以后来我才改为双queue解法。
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
c*t
114 楼
你这个能过大数据吗？
【在 p****e 的大作中提到】
: 发个不用'a'-'z'的方法，第一题
: class Solution {
: public:
: bool diff1(string &s1, string &s2)
: {
: int diff = 0;
: //if(s1.size() != s2.size()) return false;
: for(int i = 0; i < s1.size(); ++i)
: {
: if(s1[i] != s2[i])
【在 p****e 的大作中提到】
: 发个不用'a'-'z'的方法，第一题
: class Solution {
: public:
: bool diff1(string &s1, string &s2)
: {
: int diff = 0;
: //if(s1.size() != s2.size()) return false;
: for(int i = 0; i < s1.size(); ++i)
: {
: if(s1[i] != s2[i])
c*t
115 楼
你用的是dfs?
【在 j********g 的大作中提到】
: 第二个过了Large的 轻拍
: class Solution {
: public:
: vector> findLadders(string start, string end, unordered_
: set &dict) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int size=dict.size();
: int res=1;
: int done=0;
【在 j********g 的大作中提到】
: 第二个过了Large的 轻拍
: class Solution {
: public:
: vector
: set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int size=dict.size();
: int res=1;
: int done=0;
p*e
116 楼
能啊，1580ms
【在 c********t 的大作中提到】
: 你这个能过大数据吗？
【在 c********t 的大作中提到】
: 你这个能过大数据吗？
c*t
117 楼
因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
【在 p****e 的大作中提到】
: 能啊，1580ms
【在 p****e 的大作中提到】
: 能啊，1580ms
p*e
118 楼
不是每次都遍历字典，是每次循环后字典长度都会减少的
修改了一下，第二题也通过OJ large了，不过有点长，就不贴了
大）
【在 c********t 的大作中提到】
: 因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
修改了一下，第二题也通过OJ large了，不过有点长，就不贴了
大）
【在 c********t 的大作中提到】
: 因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
c*t
119 楼
看明白了.
1.遍历 构造map
2.由map, backtrack重建pathes
我模仿的写了一个java的，真的过了。1592ms
虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
多path吧(每个node都要建一个path)，读写太多了，而这个解法存的是edges(每个node
只用存parent nodes),读写少些。
【在 i**********e 的大作中提到】
: word ladder II 有人过了 large tests 吗？
: 我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
: 思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
: 整个程序不到50行。
: 基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
: 差很多。但路径组合没那么多，所以性能上也没什么影响。
: typedef unordered_multimap Map;
: typedef pair PairIter;
: vector> findLadders(string start, string end, unordered_set<
: string> &dict) {
1.遍历 构造map
2.由map, backtrack重建pathes
我模仿的写了一个java的，真的过了。1592ms
虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
多path吧(每个node都要建一个path)，读写太多了，而这个解法存的是edges(每个node
只用存parent nodes),读写少些。
【在 i**********e 的大作中提到】
: word ladder II 有人过了 large tests 吗？
: 我抛砖引玉一下吧，希望有大牛可以提出更好的解法。
: 思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下，果然简洁很多，
: 整个程序不到50行。
: 基于程序可读性，所以 bottom up 返回路径，产生了很多不必要的拷贝而导致效率会
: 差很多。但路径组合没那么多，所以性能上也没什么影响。
: typedef unordered_multimap
: typedef pair
: vector
: string> &dict) {
c*5
120 楼
Could you post your java version code? Thanks a lot.
node
【在 c********t 的大作中提到】
: 看明白了.
: 1.遍历 构造map
: 2.由map, backtrack重建pathes
: 我模仿的写了一个java的，真的过了。1592ms
: 虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
: 多path吧(每个node都要建一个path)，读写太多了，而这个解法存的是edges(每个node
: 只用存parent nodes),读写少些。
node
【在 c********t 的大作中提到】
: 看明白了.
: 1.遍历 构造map
: 2.由map, backtrack重建pathes
: 我模仿的写了一个java的，真的过了。1592ms
: 虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
: 多path吧(每个node都要建一个path)，读写太多了，而这个解法存的是edges(每个node
: 只用存parent nodes),读写少些。
f*t
121 楼
相当丑陋的BFS，已经尽量去除copy string的时间了，但还是超时，求指点T_T
class Path {
public:
Path() { path = new vector; }
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector(*path);
return np;
}
vector *path;
};
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
vector> ans;
queue q;
Path *np = new Path;
np->path->push_back(&start);
q.push(np);
unordered_set used;
queue levelUsed;
while (!q.empty()) {
int n = q.size();
while (n-- > 0) {
Path *p = q.front();
string temp(*p->path->back());
for (int i = 0; i < temp.size(); i++) {
char tc = temp[i];
for (int j = 0; j < 26; j++) {
if (tc == (char)('a' + j))
continue;
temp[i] = (char)('a' + j);
unordered_set::iterator it = dict.find(temp);
if (it != dict.end() && used.find(&(*it)) == used.
end()) {
np = p->duplicate();
np->path->push_back(&(*it));
if (temp == end) {
vector line;
for (vector::iterator itv =
np->path->begin(); itv != np->path->end(); itv++)
line.push_back(**itv);
ans.push_back(line);
}
q.push(np);
levelUsed.push(&(*it));
}
}
temp[i] = tc;
}
q.pop();
delete p;
}
if (!ans.empty())
break;
while(!levelUsed.empty()) {
used.insert(levelUsed.front());
levelUsed.pop();
}
}
return ans;
}
};
class Path {
public:
Path() { path = new vector
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector
return np;
}
vector
};
class Solution {
public:
vector
set
vector
queue
Path *np = new Path;
np->path->push_back(&start);
q.push(np);
unordered_set
queue
while (!q.empty()) {
int n = q.size();
while (n-- > 0) {
Path *p = q.front();
string temp(*p->path->back());
for (int i = 0; i < temp.size(); i++) {
char tc = temp[i];
for (int j = 0; j < 26; j++) {
if (tc == (char)('a' + j))
continue;
temp[i] = (char)('a' + j);
unordered_set
if (it != dict.end() && used.find(&(*it)) == used.
end()) {
np = p->duplicate();
np->path->push_back(&(*it));
if (temp == end) {
vector
for (vector
np->path->begin(); itv != np->path->end(); itv++)
line.push_back(**itv);
ans.push_back(line);
}
q.push(np);
levelUsed.push(&(*it));
}
}
temp[i] = tc;
}
q.pop();
delete p;
}
if (!ans.empty())
break;
while(!levelUsed.empty()) {
used.insert(levelUsed.front());
levelUsed.pop();
}
}
return ans;
}
};
i*e
122 楼
我测试了你的程序，差不多4秒跑完所有test。
简单优化了一下变成3.5秒，还差1.5秒。
说说你duplicate 路径的时候怎么做的？
有把之前共享的路径也copy 下来了吗？
【在 f*******t 的大作中提到】
: 相当丑陋的BFS，已经尽量去除copy string的时间了，但还是超时，求指点T_T
: class Path {
: public:
: Path() { path = new vector; }
:
: ~Path() { delete path; }
:
: Path* duplicate() const {
: Path *np = new Path;
: np->path = new vector(*path);
简单优化了一下变成3.5秒，还差1.5秒。
说说你duplicate 路径的时候怎么做的？
有把之前共享的路径也copy 下来了吗？
【在 f*******t 的大作中提到】
: 相当丑陋的BFS，已经尽量去除copy string的时间了，但还是超时，求指点T_T
: class Path {
: public:
: Path() { path = new vector
:
: ~Path() { delete path; }
:
: Path* duplicate() const {
: Path *np = new Path;
: np->path = new vector
f*t
123 楼
是的，这样即使只存指针也会超时呀。准备今天写下存edge的解法
【在 i**********e 的大作中提到】
: 我测试了你的程序，差不多4秒跑完所有test。
: 简单优化了一下变成3.5秒，还差1.5秒。
: 说说你duplicate 路径的时候怎么做的？
: 有把之前共享的路径也copy 下来了吗？
【在 i**********e 的大作中提到】
: 我测试了你的程序，差不多4秒跑完所有test。
: 简单优化了一下变成3.5秒，还差1.5秒。
: 说说你duplicate 路径的时候怎么做的？
: 有把之前共享的路径也copy 下来了吗？
y*e
124 楼
DFS+pruning?
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题，求指导：
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map& current, vector>& result) {
: auto iter = prev.find(root);
: for (string str : iter->second) {
: current.push_back(str);
: if (str == start) {
: vector new_one(current.size());
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题，求指导：
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map
: auto iter = prev.find(root);
: for (string str : iter->second) {
: current.push_back(str);
: if (str == start) {
: vector
p*2
125 楼
1337你这规则从哪里来的？我怎么感觉不对呀。
【在 i**********e 的大作中提到】
: 是比较奇怪，但仔细看好规则：
: Each intermediate word must exist in the dictionary
: start 和 end 都不是 intermediate word，所以字典可有可无。
:
: ) {
b*g
126 楼
"把queue 取出来的那个字的所有可能性枚举出来。"
这句是什么意思？
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
这句是什么意思？
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
l*0
127 楼
学习了！
c*a
128 楼
word ladder I的话只要BFS就够了（java），想要大set不超时，关键就是一边加新词
进queue，一边从dict里remove掉。
进queue，一边从dict里remove掉。
l*1
129 楼
这个题用DFS怎么做？ 是IDDFS？
我用BFS，JAVA写的代码I能过，II的大数据过不了，代码和上面有人贴的很像，不知道
有什么要注意的？
我用BFS，JAVA写的代码I能过，II的大数据过不了，代码和上面有人贴的很像，不知道
有什么要注意的？
l*1
130 楼
这属于不则手段了吧。。
人家给传给你的dict你算完给人家弄没有了。。
或者就得复制一份，如果dict很大，也不是个能给人好感的方法。。。
不删也能过得去。
【在 c******a 的大作中提到】
: word ladder I的话只要BFS就够了（java），想要大set不超时，关键就是一边加新词
: 进queue，一边从dict里remove掉。
f*b
131 楼
这个方法真精妙
【在 w****x 的大作中提到】
:
: 你饶了我吧。。。
: 是不是有个unordered_map可以hash string??
z*3
132 楼
删除时候不用去已经压入queue的node对应的set里面删
那一步凭空增加了很多时间
去掉那一步之后，基本上大oj没有问题
平均时间在1900ms左右
在公司的imac上只要600ms，我机器上大概是400ms……
【在 l****1 的大作中提到】
: 这个题用DFS怎么做？ 是IDDFS？
: 我用BFS，JAVA写的代码I能过，II的大数据过不了，代码和上面有人贴的很像，不知道
: 有什么要注意的？
那一步凭空增加了很多时间
去掉那一步之后，基本上大oj没有问题
平均时间在1900ms左右
在公司的imac上只要600ms，我机器上大概是400ms……
【在 l****1 的大作中提到】
: 这个题用DFS怎么做？ 是IDDFS？
: 我用BFS，JAVA写的代码I能过，II的大数据过不了，代码和上面有人贴的很像，不知道
: 有什么要注意的？
相关阅读
女人所说的美女Re: －－－－WS vs. 张朝阳专题，勿开新楼－－－－ (转载)关于非诚勿扰那个哈佛abc, 报点料正视现实：TG体制问题 （3） (转载)Re: 娱乐一下 发几个让人崩溃的淘宝模特图 (转载)【昨天是哪个不要脸的在球场厕所里骂我?】 (转载)人妻口交陪睡抵债 反诬债主强奸这SF版的猥琐女奔过照片，长得和臭鼻涕似的 (转载)电力专家：“地球一小时”活动其实违背科学规律十年了 你们还记得他们吗？正视现实：TG体制问题 （1） (转载)Re: Peter Chao同志，作为一个房东，麻烦您别这么猥琐 (转载)我重庆市将继续狠抓学生颜色教育zz日本地震核辐射！生物变异！怪兽诞生！奥特忙出现！今天去永和吃饭，气着了 (转载)不能容忍对生命科学工作者的歧视各国关于利比亚的表态zz超酷黑熊睡袋，既舒适又安全，居家旅行必备！会吓着人不？（图国内的市政Re: 车祸之后副驾驶有责任吗 (转载)