z*********e
发帖数: 10149 | 1 现在会超时，哪个地方应该优化一下？用的BFS
本机上一秒之内就出结果了，应该没有严重的算法问题吧
public List> findLadders(String start, String end, Set
dict) {
List> lastPaths = new ArrayList<>();
if(start == null || end == null) return lastPaths;
dict.add(end);
List top = new ArrayList<>();
top.add(start);
lastPaths.add(top);
if(start.equals(end)) return lastPaths;
int wordLen = start.length();
while(!dict.isEmpty()){ // same as while(true)
List> newPaths = new ArrayList<>();
Set nextLevel = new HashSet<>();
for(List l : lastPaths){
String lastWord = l.get(l.size() - 1);
for(int i = 0; i < wordLen ; i++)
for(char c = 'a'; c <= 'z'; c++){
if(c == lastWord.charAt(i)) continue;
String newWord = lastWord.substring(0, i) + c +
lastWord.substring(i+1);
if(dict.contains(newWord)){
List ll = deepCopy(l);
ll.add(newWord);
newPaths.add(ll);
nextLevel.add(newWord);
}
}
}
if(nextLevel.isEmpty()){ // cannot proceed
List> res = new ArrayList<>();
return res;
}else{
if(nextLevel.contains(end)){
List> res = new ArrayList<>();
for(List l : newPaths){
if(l.get(l.size() -1 ).equals(end)){
res.add(l);
}
}
return res;
}else{
for(String word : nextLevel) dict.remove(word);
lastPaths = newPaths;
}
}
}
// actually unnecessary return
return new ArrayList>();
}
List deepCopy(List list){
List res = new ArrayList<>();
for(String s : list) res.add(new String(s));
return res;
} |
|
