A****L
发帖数: 138 | 1 public class WordLadderII {
public class Ladder { //Define Ladder class it's important
public Ladder parent;
public String word;
public Ladder(Ladder prev,String w) {parent=prev;word=w;}
}
public ArrayList> findLadders(String start, String end
, HashSet dict) {
ArrayList> ladders = new ArrayList
String>>();
Ladder ladder = new Ladder(null,end); //Here we look from end to
start because we need to reverse the output
Queue q = new ArrayDeque();
q.add(ladder);
int count=1; //count the number of words for each level
while(!q.isEmpty()) {
HashSet set = new HashSet();
int cur=0;
for(int i=0;i
Ladder curLadder = q.poll();
String str = curLadder.word;
for(int j=0;j
any one of 26 letters
char[] wordChar = str.toCharArray();
for(char c='a';c<='z';c++) {
wordChar[j]=c;
String s = new String(wordChar);
Ladder newLadder = new Ladder(curLadder, s);
if(s.equals(start)) {//find and add to the list
ArrayList list = new ArrayList();
while(newLadder!=null) {
list.add(newLadder.word);
newLadder=newLadder.parent;
}
ladders.add(list);
}
else if(dict.contains(s) && !s.equals(str)) {//
filter those not in dict and itself
q.add(newLadder);
set.add(s);
cur++;// increase the number of nodes of the
next level
}
}
}
}
if(ladders.size()>0) return ladders; //if found then they are
the shortest distance return
dict.removeAll(set); // avoid revisiting any nodes of parent
levels
count=cur;
}
return ladders;
}
} | j**********m
发帖数: 51 | | c********l
发帖数: 8138 | 3 简洁不是最终极的目标，有时候需要reduce runtime complexity
见我之前写的
http://www.mitbbs.com/article/JobHunting/32658475_3.html
//MITBBS' article system will mess up the source code
// You may probably need to re-arrange the line breaks
// by coupondeal@mitbbs
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Solution {
public static void main(String[] args) {
Solution sol = new Solution();
String[] dictStrArr = new String[] {
"dose","ends","dine","jars","prow","soap","guns","hops","
cray","hove","ella","hour","lens","jive","wiry","earl","mara","part","flue",
"putt","rory","bull","york","ruts","lily","vamp","bask","peer","boat","dens"
,"lyre","jets","wide","rile","boos","down","path","onyx","mows","toke","soto
","dork","nape","mans","loin","jots","male","sits","minn","sale","pets","
hugo","woke","suds","rugs","vole","warp","mite","pews","lips","pals","nigh",
"sulk","vice","clod","iowa","gibe","shad","carl","huns","coot","sera","mils"
,"rose","orly","ford","void","time","eloy","risk","veep","reps","dolt","hens
","tray","melt","rung","rich","saga","lust","yews","rode","many","cods","
rape","last","tile","nosy","take","nope","toni","bank","jock","jody","diss",
"nips","bake","lima","wore","kins","cult","hart","wuss","tale","sing","lake"
,"bogy","wigs","kari","magi","bass","pent","tost","fops","bags","duns","will
","tart","drug","gale","mold","disk","spay","hows","naps","puss","gina","
kara","zorn","boll","cams","boas","rave","sets","lego","hays","judy","chap",
"live","bahs","ohio","nibs","cuts","pups","data","kate","rump","hews","mary"
,"stow","fang","bolt","rues","mesh","mice","rise","rant","dune","jell","laws
","jove","bode","sung","nils","vila","mode","hued","cell","fies","swat","
wags","nate","wist","honk","goth","told","oise","wail","tels","sore","hunk",
"mate","luke","tore","bond","bast","vows","ripe","fond","benz","firs","zeds"
,"wary","baas","wins","pair","tags","cost","woes","buns","lend","bops","code
","eddy","siva","oops","toed","bale","hutu","jolt","rife","darn","tape","
bold","cope","cake","wisp","vats","wave","hems","bill","cord","pert","type",
"kroc","ucla","albs","yoko","silt","pock","drub","puny","fads","mull","pray"
,"mole","talc","east","slay","jamb","mill","dung","jack","lynx","nome","leos
","lade","sana","tike","cali","toge","pled","mile","mass","leon","sloe","
lube","kans","cory","burs","race","toss","mild","tops","maze","city","sadr",
"bays","poet","volt","laze","gold","zuni","shea","gags","fist","ping","pope"
,"cora","yaks","cosy","foci","plan","colo","hume","yowl","craw","pied","toga
","lobs","love","lode","duds","bled","juts","gabs","fink","rock","pant","
wipe","pele","suez","nina","ring","okra","warm","lyle","gape","bead","lead",
"jane","oink","ware","zibo","inns","mope","hang","made","fobs","gamy","fort"
,"peak","gill","dino","dina","tier"
};
HashSet dict = new HashSet ();
for (int i=0; i
dict.add(dictStrArr[i]);
}
System.out.println("begin");
long t0 = System.currentTimeMillis();
sol.findLadders("nape", "mild", dict);
long t1 = System.currentTimeMillis();
System.out.println(t1-t0);
}
ArrayList> results;
Map> reversePath;
Set toVisit;
String start; String end;
public ArrayList> findLadders(String start, String end
, HashSet dict) {
results = new ArrayList>();
reversePath = new HashMap>();
toVisit = (HashSet) dict.clone();
toVisit.add(end);
this.start = start;
this.end = end;
bfs();
ArrayList path = new ArrayList();
populateOutput(end, path);
return results;
}
private void populateOutput(String tgt, ArrayList path) {
path.add(0, tgt);
if (tgt.equals(start)) {
results.add(path);
return;
}
ArrayList srcs = reversePath.get(tgt);
if (srcs != null) {
for (int i=0; i
String srci = srcs.get(i);
ArrayList pathI = (ArrayList) path.clone();
populateOutput(srci, pathI);
}
}
}
private void bfs() {
boolean found = false;
char[] chrArr;
int wordLength = start.length(); // Cache to accelerate
ArrayList currLevel = new ArrayList();
currLevel.add(start);
while (!found) {
if (currLevel.isEmpty()) {
//No solution at all
break;
}
int currLevelSize = currLevel.size();
for (int i=0; i
toVisit.remove(currLevel.get(i));
}
ArrayList nextLevel = new ArrayList();
for (int i=0; i
String currStr = currLevel.get(i);
if (found) {
if (isDiffByOne(currStr, end, wordLength)) {
addSegment(currStr, end);
}
}
else {
outerFor:
for (int j=0; j
chrArr = currStr.toCharArray(); // reset chrArr
for (char chr = 'a'; chr<='z'; chr++) {
chrArr[j] = chr;
String candidate = new String(chrArr);
if (toVisit.contains(candidate)) {
addSegment(currStr, candidate);
if (candidate.equals(end)) {
found = true;
break outerFor;
}
else {
nextLevel.add(candidate);
}
}
}
}
}
} // for currLevel loop
currLevel = nextLevel;
}
}
private void addSegment(String src, String tgt) {
ArrayList list = reversePath.get(tgt);
if (list == null) {
list = new ArrayList();
reversePath.put(tgt, list);
list.add(src);
}
else {
if (!list.contains(src)) {
list.add(src);
}
}
}
private boolean isDiffByOne(String src, String tgt, int wordLength) {
int diff = 0;
for (int i=0; i
if (src.charAt(i)!=tgt.charAt(i)) {
if (diff>=1)
return false;
diff ++ ;
}
}
return (diff==1);
}
} | f******n
发帖数: 279 | | c*******2
发帖数: 60 | 5 说说我自己的看法.
首先我同意三楼的, 代码长短不是最重要的, 还得看效率.
楼主的代码确实短, 想必花了心思压缩.
但我觉得有几个问题.
一个问题是每个Ladder object有只有一个prev指针.
这种情况下, 如果某个单词在很多个ladder里面出现的话, 必须要构造很多个Ladder
objects. 不知这样的空间效率如何.
第二个问题是第一个while循环的终止条件是queue是empty的, 如果我没理解错的话.
这样即使是找到了start, 循环还会继续下去. 因为楼主在dict里把出现过的单词都
remove了, 循环必定会终止而且也不会出现更长的ladder. 算法是正确的, 但终止时间
可能会晚了点. 应该在找到start后就可以终止下一个level的循环了.
第三个问题是修改了dict...这个不重要, 可以像三楼那样clone一个就行. 我个人是用
了个hashmap保存已经visit过的word, 因为我的这个hashmap还有其他用处,所以也就顺
便用在这里, 没有clone.
ps三楼: 我看你在你的帖子里说你的代码跑大数据是485ms. 我用我的代码跑了下是70-
110ms.
我的代码在
https://github.com/chen1502/LeetCode/blob/master/wordLadderII.java | A****L
发帖数: 138 | 6 谢谢你的意见。 我也肯定是同意效率要高才行的。我的意思是在保证效率的前提下，
越简单越好。 具体到这题，基本前提就是能pass OJ。另外要是代码让人容易理解就更
好了。 我的code 的思路就是 一层一层 推进， 如果在到达某层找到了 path 那么到
这层 所有可行的path 都是最短的，然后就直接返回结果了。具体就是下面这个语句。
if(ladders.size()>0) return ladders;
//if found then they are the shortest distance return
虽然 while 终止条件是 empty 但是某一层找到了就返回结果了。
每个ladder 只记录它是从哪个ladder 下来的。 如果一个ladder 下来有很多
children ladder， 那么这个ladder 可能出现在很多path 里，但是这里不会重新产生
ladder object， 只有一个ladder object。 因为所有的children 都指向了它（同一
个object）。
空间存储上，如果clone 记录visited 那么一直是会存在两个dict了。
这里直接在原来的dict 上操作，不需要额外一个size 的dict。 而且随着层数的增加
，size 在变小。 当然如果题目要求不能改变原来的dict。 那就备份一个。这样跟用
hashmap 记录 visited 效率应该一样了就。
谢谢。
【在 c*******2 的大作中提到】
: 说说我自己的看法.
: 首先我同意三楼的, 代码长短不是最重要的, 还得看效率.
: 楼主的代码确实短, 想必花了心思压缩.
: 但我觉得有几个问题.
: 一个问题是每个Ladder object有只有一个prev指针.
: 这种情况下, 如果某个单词在很多个ladder里面出现的话, 必须要构造很多个Ladder
: objects. 不知这样的空间效率如何.
: 第二个问题是第一个while循环的终止条件是queue是empty的, 如果我没理解错的话.
: 这样即使是找到了start, 循环还会继续下去. 因为楼主在dict里把出现过的单词都
: remove了, 循环必定会终止而且也不会出现更长的ladder. 算法是正确的, 但终止时间
| c********l
发帖数: 8138 | 7 485ms是之前疏忽了用arraylist的时间
换成hashset之后就是<100ms
我自己的机器上也是100ms 左右，只不过这个结果好像没放在原贴里面
70-
【在 c*******2 的大作中提到】
: 说说我自己的看法.
: 首先我同意三楼的, 代码长短不是最重要的, 还得看效率.
: 楼主的代码确实短, 想必花了心思压缩.
: 但我觉得有几个问题.
: 一个问题是每个Ladder object有只有一个prev指针.
: 这种情况下, 如果某个单词在很多个ladder里面出现的话, 必须要构造很多个Ladder
: objects. 不知这样的空间效率如何.
: 第二个问题是第一个while循环的终止条件是queue是empty的, 如果我没理解错的话.
: 这样即使是找到了start, 循环还会继续下去. 因为楼主在dict里把出现过的单词都
: remove了, 循环必定会终止而且也不会出现更长的ladder. 算法是正确的, 但终止时间
| c********l
发帖数: 8138 | 8 你放在github上的代码跑得快，还是我的代码跑得快？相差多少？
（不是为了比赛，呵呵，为了提高）
https://github.com/chen1502/LeetCode/blob/master/wordLadderII.java
【在 c*******2 的大作中提到】
: 说说我自己的看法.
: 首先我同意三楼的, 代码长短不是最重要的, 还得看效率.
: 楼主的代码确实短, 想必花了心思压缩.
: 但我觉得有几个问题.
: 一个问题是每个Ladder object有只有一个prev指针.
: 这种情况下, 如果某个单词在很多个ladder里面出现的话, 必须要构造很多个Ladder
: objects. 不知这样的空间效率如何.
: 第二个问题是第一个while循环的终止条件是queue是empty的, 如果我没理解错的话.
: 这样即使是找到了start, 循环还会继续下去. 因为楼主在dict里把出现过的单词都
: remove了, 循环必定会终止而且也不会出现更长的ladder. 算法是正确的, 但终止时间
| c*******2
发帖数: 60 | 9 我在我电脑上测试了下.
用你那个帖子里的大数据的话, 我的是100ms左右(测试多次), 你和楼主的都是200左右.
然后我自己弄了个test case, dict里包含了所有长度为4的String, 也就是有26^4个
words. 然后随便弄了两个没有重复字母的单词, 比如abcd, efgh. 这回我和你的时间
差不多2000ms, 楼主的到了13000ms
【在 c********l 的大作中提到】
: 你放在github上的代码跑得快，还是我的代码跑得快？相差多少？
: （不是为了比赛，呵呵，为了提高）
:
: https://github.com/chen1502/LeetCode/blob/master/wordLadderII.java
| c********l
发帖数: 8138 | 10 不对啊，
你前面说用我贴子里面的大数据，我的code是100ms出头一些，怎么又变成200ms了？
另外，假定的确像你说的，中等数据有2倍的差距。
那么相对于我的code，你的code优化在哪儿？
右.
【在 c*******2 的大作中提到】
: 我在我电脑上测试了下.
: 用你那个帖子里的大数据的话, 我的是100ms左右(测试多次), 你和楼主的都是200左右.
: 然后我自己弄了个test case, dict里包含了所有长度为4的String, 也就是有26^4个
: words. 然后随便弄了两个没有重复字母的单词, 比如abcd, efgh. 这回我和你的时间
: 差不多2000ms, 楼主的到了13000ms
| | | c*******2
发帖数: 60 | 11 哦, 对, 是在找到结果就终止了.
空间上我还是觉得重复了.
比如 start = "abcd", end = "efgh".
dict 是所有长度为4的string.
那么中间的每个字母的indegree和outdegree都大于1.
比如: "abcd" -> "ebcd" -> "efcd" -> "efgd" -> "efgh"
"abcd" -> "afcd" -> "efcd" -> "efch" -> "efgh"
由于你只有一个pointer, "efcd"这个Ladder object至少要创建两次, 不管这个
pointer是指向前还是后.
。
【在 A****L 的大作中提到】
: 谢谢你的意见。 我也肯定是同意效率要高才行的。我的意思是在保证效率的前提下，
: 越简单越好。 具体到这题，基本前提就是能pass OJ。另外要是代码让人容易理解就更
: 好了。 我的code 的思路就是 一层一层 推进， 如果在到达某层找到了 path 那么到
: 这层 所有可行的path 都是最短的，然后就直接返回结果了。具体就是下面这个语句。
: if(ladders.size()>0) return ladders;
: //if found then they are the shortest distance return
: 虽然 while 终止条件是 empty 但是某一层找到了就返回结果了。
: 每个ladder 只记录它是从哪个ladder 下来的。 如果一个ladder 下来有很多
: children ladder， 那么这个ladder 可能出现在很多path 里，但是这里不会重新产生
: ladder object， 只有一个ladder object。 因为所有的children 都指向了它（同一
| A****L
发帖数: 138 | 12 对的，你这个问题很好。的确是如果两个word 是不同的路径上的话 是会单独一个
ladder object。不然会交叉了。 我再看看能不能改进。 谢谢。 另外你们说的test
时间问题。 不知道你们在 leetcode 上run所有cases 的时间是多少。 我的run time
显示的是1456 ms
【在 c*******2 的大作中提到】
: 哦, 对, 是在找到结果就终止了.
: 空间上我还是觉得重复了.
: 比如 start = "abcd", end = "efgh".
: dict 是所有长度为4的string.
: 那么中间的每个字母的indegree和outdegree都大于1.
: 比如: "abcd" -> "ebcd" -> "efcd" -> "efgd" -> "efgh"
: "abcd" -> "afcd" -> "efcd" -> "efch" -> "efgh"
: 由于你只有一个pointer, "efcd"这个Ladder object至少要创建两次, 不管这个
: pointer是指向前还是后.
:
| A****L
发帖数: 138 | 13 run了下你的code 的确要比我的快不少。我学习下，看看能不能结合下。 皆能简洁又
能和你的一样快。
【在 c*******2 的大作中提到】
: 哦, 对, 是在找到结果就终止了.
: 空间上我还是觉得重复了.
: 比如 start = "abcd", end = "efgh".
: dict 是所有长度为4的string.
: 那么中间的每个字母的indegree和outdegree都大于1.
: 比如: "abcd" -> "ebcd" -> "efcd" -> "efgd" -> "efgh"
: "abcd" -> "afcd" -> "efcd" -> "efch" -> "efgh"
: 由于你只有一个pointer, "efcd"这个Ladder object至少要创建两次, 不管这个
: pointer是指向前还是后.
:
| l*******b
发帖数: 2586 | 14 这个心中永远的痛呀。。。最早二爷的那个程序短而且快。学习写了两三个版本，纸上
过了两遍，被面到的时候居然没写好。。。
这里写了个javascript版的，小伙伴们别像那个state machine版的valid number一样
揪出来批斗了呀。。。
http://nodejs-luckynoob.rhcloud.com/apps/jsapps.html | c********l
发帖数: 8138 | 15 statemachine版？
【在 l*******b 的大作中提到】
: 这个心中永远的痛呀。。。最早二爷的那个程序短而且快。学习写了两三个版本，纸上
: 过了两遍，被面到的时候居然没写好。。。
: 这里写了个javascript版的，小伙伴们别像那个state machine版的valid number一样
: 揪出来批斗了呀。。。
: http://nodejs-luckynoob.rhcloud.com/apps/jsapps.html
| a*****n
发帖数: 158 | | l*******b
发帖数: 2586 | 17 http://www.mitbbs.com/article_t/JobHunting/32675497.html
就是这个呀，过一阵子就被拿来批斗一番。。。
【在 c********l 的大作中提到】
: statemachine版？
| A****L
发帖数: 138 | 18 优化后的代码。 速度和你的差不多了。
https://github.com/notbrucelee/Leetcode/blob/master/WordLadderII.java
【在 c*******2 的大作中提到】
: 哦, 对, 是在找到结果就终止了.
: 空间上我还是觉得重复了.
: 比如 start = "abcd", end = "efgh".
: dict 是所有长度为4的string.
: 那么中间的每个字母的indegree和outdegree都大于1.
: 比如: "abcd" -> "ebcd" -> "efcd" -> "efgd" -> "efgh"
: "abcd" -> "afcd" -> "efcd" -> "efch" -> "efgh"
: 由于你只有一个pointer, "efcd"这个Ladder object至少要创建两次, 不管这个
: pointer是指向前还是后.
:
| f****8
发帖数: 33 | 19 Thanks sharing!
The key point for this problem is that how to discover the neighbor nodes:
Find the neighbor nodes by constructing and searching them in the dict (for
each found node in last round, need 25 x strlen times string comparing),
rather than enumerating all the remain nodes in the dict (for each found
node in last round, need dict.size() comparing). | m*********y
发帖数: 111 | |
|
