p****e
发帖数: 3548 | |
w****x
发帖数: 2483 | 2 这题怎么那么别扭，原来目标单词不在字典里...
还有我咋超时了... |
i**********e
发帖数: 1145 | |
w****x
发帖数: 2483 | 4 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;
}
}; |
i**********e
发帖数: 1145 | |
p*****p
发帖数: 379 | 6 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;
}
}; |
i**********e
发帖数: 1145 | 7 关于怎么测下一步是不是合法：
每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
了。 |
a***o
发帖数: 1182 | 8 我来贴个能过的,比较丑,大家见谅...
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
|
w****x
发帖数: 2483 | 9
) {
这个也超时了
【在 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;
|
i**********e
发帖数: 1145 | 10 是比较奇怪，但仔细看好规则：
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;
|
|
|
w****x
发帖数: 2483 | 11
没看明白..
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
|
a***o
发帖数: 1182 | 12 就是先变再到查词典查 VS. 先从词典抓一个再查是不是只变了一个字母
【在 w****x 的大作中提到】
:
: 没看明白..
|
i**********e
发帖数: 1145 | 13 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
【在 w****x 的大作中提到】
:
: 没看明白..
|
w****x
发帖数: 2483 | 14
这个啊，没意思，太tricky了
【在 a***o 的大作中提到】
: 就是先变再到查词典查 VS. 先从词典抓一个再查是不是只变了一个字母
|
a***o
发帖数: 1182 | 15 leetcode大侠,能不能指点一下这个ladder2怎么做啊
DFS能过么?还是要BFS+记路径?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
|
w****x
发帖数: 2483 | 16
感觉正常的思路是有一步pre processing,就是先把dict建图，
然后后续的查询ladder从建好的图为出发点。
这个图可以用map表示
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
|
w****x
发帖数: 2483 | 17
用map>记录路径，然后递归输出吧
wordladder2 太麻烦了，不做了,string的hash map还得自己写
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
|
a***o
发帖数: 1182 | 18 是啊,搞了个递归超时了,
看来得上bfs+map,不知道会不会超mem
【在 w****x 的大作中提到】
:
: 用map>记录路径，然后递归输出吧
: wordladder2 太麻烦了，不做了,string的hash map还得自己写
|
i**********e
发帖数: 1145 | 19 DFS 肯定过不了。最长的ladder length 是 42。
BFS + 记路径是正解。
但怎么记路径使得空间少 + 重建路径是比较tricky。
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
|
a***o
发帖数: 1182 | 20 多谢,再去琢磨琢磨
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
|
|
|
w****x
发帖数: 2483 | 21
BFS然后构建map>结构，输出路径还是得递归吧
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
|
i**********e
发帖数: 1145 | 22 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
start。其实输出
路径不用递归也可以，比较麻烦一些就是了。
【在 w****x 的大作中提到】
:
: BFS然后构建map>结构，输出路径还是得递归吧
|
w****x
发帖数: 2483 | 23
你饶了我吧。。。
是不是有个unordered_map可以hash string??
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
|
i**********e
发帖数: 1145 | 24 你要的是 unordered_multimap 吧。
一个 key 可以 map 到好几个 value. |
p*****p
发帖数: 379 | 25 原来是这样
这题在CC上有，但是没仔细看过，现在回头看原来是这么回事，学习了
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
|
f*******t
发帖数: 7549 | 26 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;
} |
b*****u
发帖数: 648 | |
x*******6
发帖数: 262 | |
P*******b
发帖数: 1001 | 29 "hot", "hot", ["hot","dot"]
不明白这个为什么结果是3
【在 p****e 的大作中提到】
: rt
|
g***9
发帖数: 159 | 30 写了一个能过大数据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;
}
}; |
|
|
d*********g
发帖数: 154 | |
c*****a
发帖数: 808 | 32 写了个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
for(char j = 'a'; j<='z';j++){
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
发帖数: 1145 | 33 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;
} |
d******e
发帖数: 164 | 34 贴个第一题，
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
|
w*****t
发帖数: 485 | 35 career 150上有这个题，解法就是 BFS + hashmap存路径，算是标准的解法把。 |
j********g
发帖数: 80 | 36 第二个过了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
for(char s='a';s<='z';s++){
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
string> > &path, vector > &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
getpath(start, up[i], path, rtn, route);
}
}
}; |
c********t
发帖数: 5706 | 37 大侠。
我刚开始做第一题，用的是一贯的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
发帖数: 1145 | 38 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, 所以能提前退出？
: 多谢！
|
i**********e
发帖数: 1145 | 39 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, 所以能提前退出？
: 多谢！
|
c********t
发帖数: 5706 | 40 是的，过了。多谢多谢！
【在 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
发帖数: 1293 | 41 看不懂阿。
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
|
c*****a
发帖数: 808 | 42 res是我在local ide测试时用看的.可以直接用counter就行
path是用来记录哪个词变换的
cc150有这题啊
【在 h**********y 的大作中提到】
: 看不懂阿。
: path和res的作用感觉有问题阿。。
:
: ) {
|
t********6
发帖数: 348 | 43 第二题，求指导：
class Solution {
public:
void traverse(string& start, string& root, unordered_map
string> >& prev, vector& 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;
}
}; |
c********t
发帖数: 5706 | 44 多谢！
第一题最后发现用 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
String>>();
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
char och=str[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
>(path);
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList newPath = new ArrayList
>(path);
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
发帖数: 3548 | 45 发个不用'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
sizeofmap!=nc)
{
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
发帖数: 5706 | 46 我想到这个解法，可是 start to a string可以有多个路径，那hashmap
vector>岂不是不行？需要hashmap>>?
还有一个是麻烦，而且要存所有路径很耗费mem，难道完成BFS 一个level以后，还要
remove them from hashmap?
所以后来我才改为双queue解法。
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
|
c********t
发帖数: 5706 | 47 你这个能过大数据吗？
【在 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
发帖数: 5706 | 48 你用的是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;
|
p****e
发帖数: 3548 | 49 能啊，1580ms
【在 c********t 的大作中提到】
: 你这个能过大数据吗？
|
c********t
发帖数: 5706 | 50 因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
【在 p****e 的大作中提到】
: 能啊，1580ms
|
|
|
p****e
发帖数: 3548 | 51 不是每次都遍历字典，是每次循环后字典长度都会减少的
修改了一下，第二题也通过OJ large了，不过有点长，就不贴了
大）
【在 c********t 的大作中提到】
: 因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
|
c********t
发帖数: 5706 | 52 看明白了.
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) {
|
c******5
发帖数: 84 | 53 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),读写少些。
|
f*******t
发帖数: 7549 | 54 相当丑陋的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;
}
}; |
i**********e
发帖数: 1145 | 55 我测试了你的程序，差不多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);
|
f*******t
发帖数: 7549 | 56 是的，这样即使只存指针也会超时呀。准备今天写下存edge的解法
【在 i**********e 的大作中提到】
: 我测试了你的程序，差不多4秒跑完所有test。
: 简单优化了一下变成3.5秒，还差1.5秒。
: 说说你duplicate 路径的时候怎么做的？
: 有把之前共享的路径也copy 下来了吗？
|
y****e
发帖数: 1012 | 57 DFS+pruning?
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题，求指导：
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map: string> >& prev, vector& 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());
|
p*****2
发帖数: 21240 | 58
1337你这规则从哪里来的？我怎么感觉不对呀。
【在 i**********e 的大作中提到】
: 是比较奇怪，但仔细看好规则：
: Each intermediate word must exist in the dictionary
: start 和 end 都不是 intermediate word，所以字典可有可无。
:
: ) {
|
p****e
发帖数: 3548 | |
w****x
发帖数: 2483 | 60 这题怎么那么别扭，原来目标单词不在字典里...
还有我咋超时了... |
|
|
i**********e
发帖数: 1145 | |
w****x
发帖数: 2483 | 62 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;
}
}; |
i**********e
发帖数: 1145 | |
p*****p
发帖数: 379 | 64 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;
}
}; |
i**********e
发帖数: 1145 | 65 关于怎么测下一步是不是合法：
每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
了。 |
a***o
发帖数: 1182 | 66 我来贴个能过的,比较丑,大家见谅...
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
|
w****x
发帖数: 2483 | 67
) {
这个也超时了
【在 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;
|
i**********e
发帖数: 1145 | 68 是比较奇怪，但仔细看好规则：
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;
|
w****x
发帖数: 2483 | 69
没看明白..
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
|
a***o
发帖数: 1182 | 70 就是先变再到查词典查 VS. 先从词典抓一个再查是不是只变了一个字母
【在 w****x 的大作中提到】
:
: 没看明白..
|
|
|
i**********e
发帖数: 1145 | 71 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
【在 w****x 的大作中提到】
:
: 没看明白..
|
w****x
发帖数: 2483 | 72
这个啊，没意思，太tricky了
【在 a***o 的大作中提到】
: 就是先变再到查词典查 VS. 先从词典抓一个再查是不是只变了一个字母
|
a***o
发帖数: 1182 | 73 leetcode大侠,能不能指点一下这个ladder2怎么做啊
DFS能过么?还是要BFS+记路径?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
|
w****x
发帖数: 2483 | 74
感觉正常的思路是有一步pre processing,就是先把dict建图，
然后后续的查询ladder从建好的图为出发点。
这个图可以用map表示
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
|
w****x
发帖数: 2483 | 75
用map>记录路径，然后递归输出吧
wordladder2 太麻烦了，不做了,string的hash map还得自己写
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
|
a***o
发帖数: 1182 | 76 是啊,搞了个递归超时了,
看来得上bfs+map,不知道会不会超mem
【在 w****x 的大作中提到】
:
: 用map>记录路径，然后递归输出吧
: wordladder2 太麻烦了，不做了,string的hash map还得自己写
|
i**********e
发帖数: 1145 | 77 DFS 肯定过不了。最长的ladder length 是 42。
BFS + 记路径是正解。
但怎么记路径使得空间少 + 重建路径是比较tricky。
【在 a***o 的大作中提到】
: leetcode大侠,能不能指点一下这个ladder2怎么做啊
: DFS能过么?还是要BFS+记路径?
: 多谢!
|
a***o
发帖数: 1182 | 78 多谢,再去琢磨琢磨
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
|
w****x
发帖数: 2483 | 79
BFS然后构建map>结构，输出路径还是得递归吧
【在 i**********e 的大作中提到】
: DFS 肯定过不了。最长的ladder length 是 42。
: BFS + 记路径是正解。
: 但怎么记路径使得空间少 + 重建路径是比较tricky。
|
i**********e
发帖数: 1145 | 80 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
start。其实输出
路径不用递归也可以，比较麻烦一些就是了。
【在 w****x 的大作中提到】
:
: BFS然后构建map>结构，输出路径还是得递归吧
|
|
|
w****x
发帖数: 2483 | 81
你饶了我吧。。。
是不是有个unordered_map可以hash string??
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
|
i**********e
发帖数: 1145 | 82 你要的是 unordered_multimap 吧。
一个 key 可以 map 到好几个 value. |
p*****p
发帖数: 379 | 83 原来是这样
这题在CC上有，但是没仔细看过，现在回头看原来是这么回事，学习了
【在 i**********e 的大作中提到】
: 关于怎么测下一步是不是合法：
: 每一个字母'a'-'z'遍历，再看是否在字典里的复杂度 = 26 * n (n = 字的长度）
: unordered_set 的查询是 O(1) 的。
: 遍历所有字典里的字然后一个一个比较是 n * dictionary_size，复杂度自然就上去
: 了。
|
f*******t
发帖数: 7549 | 84 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;
} |
b*****u
发帖数: 648 | |
x*******6
发帖数: 262 | |
P*******b
发帖数: 1001 | 87 "hot", "hot", ["hot","dot"]
不明白这个为什么结果是3
【在 p****e 的大作中提到】
: rt
|
g***9
发帖数: 159 | 88 写了一个能过大数据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;
}
}; |
d*********g
发帖数: 154 | |
c*****a
发帖数: 808 | 90 写了个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
for(char j = 'a'; j<='z';j++){
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
发帖数: 1145 | 91 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;
} |
d******e
发帖数: 164 | 92 贴个第一题，
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
|
w*****t
发帖数: 485 | 93 career 150上有这个题，解法就是 BFS + hashmap存路径，算是标准的解法把。 |
j********g
发帖数: 80 | 94 第二个过了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
for(char s='a';s<='z';s++){
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
string> > &path, vector > &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
getpath(start, up[i], path, rtn, route);
}
}
}; |
c********t
发帖数: 5706 | 95 大侠。
我刚开始做第一题，用的是一贯的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
发帖数: 1145 | 96 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, 所以能提前退出？
: 多谢！
|
i**********e
发帖数: 1145 | 97 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, 所以能提前退出？
: 多谢！
|
c********t
发帖数: 5706 | 98 是的，过了。多谢多谢！
【在 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
发帖数: 1293 | 99 看不懂阿。
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
|
c*****a
发帖数: 808 | 100 res是我在local ide测试时用看的.可以直接用counter就行
path是用来记录哪个词变换的
cc150有这题啊
【在 h**********y 的大作中提到】
: 看不懂阿。
: path和res的作用感觉有问题阿。。
:
: ) {
|
|
|
t********6
发帖数: 348 | 101 第二题，求指导：
class Solution {
public:
void traverse(string& start, string& root, unordered_map
string> >& prev, vector& 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;
}
}; |
c********t
发帖数: 5706 | 102 多谢！
第一题最后发现用 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
String>>();
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
char och=str[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
>(path);
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList newPath = new ArrayList
>(path);
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
发帖数: 3548 | 103 发个不用'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
sizeofmap!=nc)
{
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
发帖数: 5706 | 104 我想到这个解法，可是 start to a string可以有多个路径，那hashmap
vector>岂不是不行？需要hashmap>>?
还有一个是麻烦，而且要存所有路径很耗费mem，难道完成BFS 一个level以后，还要
remove them from hashmap?
所以后来我才改为双queue解法。
【在 i**********e 的大作中提到】
: 牛呀，那么快就想到了。不愧800题大牛。这思路是对的。输出路径就想等于从end返回
: start。其实输出
: 路径不用递归也可以，比较麻烦一些就是了。
|
c********t
发帖数: 5706 | 105 你这个能过大数据吗？
【在 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
发帖数: 5706 | 106 你用的是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;
|
p****e
发帖数: 3548 | 107 能啊，1580ms
【在 c********t 的大作中提到】
: 你这个能过大数据吗？
|
c********t
发帖数: 5706 | 108 因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
【在 p****e 的大作中提到】
: 能啊，1580ms
|
p****e
发帖数: 3548 | 109 不是每次都遍历字典，是每次循环后字典长度都会减少的
修改了一下，第二题也通过OJ large了，不过有点长，就不贴了
大）
【在 c********t 的大作中提到】
: 因为看你好像每次都遍历字典，ihasleetcode前面解释了这样会超时。（字典可以很大）
|
c********t
发帖数: 5706 | 110 看明白了.
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) {
|
|
|
c******5
发帖数: 84 | 111 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),读写少些。
|
f*******t
发帖数: 7549 | 112 相当丑陋的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;
}
}; |
i**********e
发帖数: 1145 | 113 我测试了你的程序，差不多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);
|
f*******t
发帖数: 7549 | 114 是的，这样即使只存指针也会超时呀。准备今天写下存edge的解法
【在 i**********e 的大作中提到】
: 我测试了你的程序，差不多4秒跑完所有test。
: 简单优化了一下变成3.5秒，还差1.5秒。
: 说说你duplicate 路径的时候怎么做的？
: 有把之前共享的路径也copy 下来了吗？
|
y****e
发帖数: 1012 | 115 DFS+pruning?
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题，求指导：
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map: string> >& prev, vector& 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());
|
p*****2
发帖数: 21240 | 116
1337你这规则从哪里来的？我怎么感觉不对呀。
【在 i**********e 的大作中提到】
: 是比较奇怪，但仔细看好规则：
: Each intermediate word must exist in the dictionary
: start 和 end 都不是 intermediate word，所以字典可有可无。
:
: ) {
|
b****g
发帖数: 192 | 117 "把queue 取出来的那个字的所有可能性枚举出来。"
这句是什么意思？
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
: 这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
: efficient，只有查询最适合。
: 倒过来思考：
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。
|
l*******0
发帖数: 63 | |
c******a
发帖数: 789 | 119 word ladder I的话只要BFS就够了（java），想要大set不超时，关键就是一边加新词
进queue，一边从dict里remove掉。 |
l****1
发帖数: 19 | 120 这个题用DFS怎么做？ 是IDDFS？
我用BFS，JAVA写的代码I能过，II的大数据过不了，代码和上面有人贴的很像，不知道
有什么要注意的？ |
|
|
l****1
发帖数: 19 | 121
这属于不则手段了吧。。
人家给传给你的dict你算完给人家弄没有了。。
或者就得复制一份，如果dict很大，也不是个能给人好感的方法。。。
不删也能过得去。
【在 c******a 的大作中提到】
: word ladder I的话只要BFS就够了（java），想要大set不超时，关键就是一边加新词
: 进queue，一边从dict里remove掉。
|
f*******b
发帖数: 520 | 122
这个方法真精妙
【在 w****x 的大作中提到】
:
: 你饶了我吧。。。
: 是不是有个unordered_map可以hash string??
|
z*******3
发帖数: 13709 | 123 删除时候不用去已经压入queue的node对应的set里面删
那一步凭空增加了很多时间
去掉那一步之后，基本上大oj没有问题
平均时间在1900ms左右
在公司的imac上只要600ms，我机器上大概是400ms……
【在 l****1 的大作中提到】
: 这个题用DFS怎么做？ 是IDDFS？
: 我用BFS，JAVA写的代码I能过，II的大数据过不了，代码和上面有人贴的很像，不知道
: 有什么要注意的？
|
