【每日一囧137】小二哥,好个相貌,老衲喜欢你好久了 (转载)# Joke - 肚皮舞运动
A*L
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;
}
}
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
, HashSet
ArrayList
Ladder ladder = new Ladder(null,end); //Here we look from end to
start because we need to reverse the output
Queue
q.add(ladder);
int count=1; //count the number of words for each level
while(!q.isEmpty()) {
HashSet
int cur=0;
for(int i=0;i
String str = curLadder.word;
for(int j=0;j
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
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;
}
}