B*******j
发帖数: 232 | 1 就用的bfs，可是就是通过不了测试，请帮忙看看我这个办法，怎么过不去呢？ 先谢
过了
public class Solution {
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return an integer
*/
public int ladderLength(String start, String end, Set dict) {
// write your code here
int len = dict.size();
if(len < 1){
return 0;
}
Queue q = new LinkedList();
int count = 2;
for(String s : dict){
if(checkNext(start, s)){
if(s.equals(end)){
return count;
}
q.add(s);
}
}
while(!q.isEmpty()){
int qSize = q.size();
for(int i=0; i< qSize; i++){
String currStr = q.poll();
if(checkNext(currStr, end)){
return count+1;
}
for(String s : dict){
if(q.contains(s)){
continue;
}
if(checkNext(currStr, s)){
q.add(s);
}
}
dict.remove(currStr);
}
count++;
}
return count;
}
private boolean checkNext(String str1, String str2){
if(str1.length() != str2.length()){
return false;
}else{
int count = 0;
for(int i=0; i
if(str1.charAt(i)!=str2.charAt(i)){
count++;
}
}
if(count != 1){
return false;
}else{
return true;
}
}
}
} | z*****5
发帖数: 72 | 2 42-49行 这里可以从currStr直接生成next字符串 暴力改变每个位置的每个字符就行
这段的复杂度可以从O(N)降低成O(len(currStr)) | S**********n
发帖数: 250 | 3 赞
：42-49行 这里可以从currStr直接生成next字符串 暴力改变每个位置的每个字符就行
： | S********t
发帖数: 3431 | 4 更好的方法是，把每个词映射到该词遮住某个位置的变种上, eg.:
"hat"-> "?at", "h?t", "ha?"
"had"-> "?ad", "h?d", "ha?"
用一些preprocess的时间空间(hashmultimap)，就可以很快的lookup neighbor。
当然你尝试所有26个字母也是O(1),复杂度其实是一样的，不过这个常数上的加速在实
际中也是很有用的。
【在 z*****5 的大作中提到】
: 42-49行 这里可以从currStr直接生成next字符串 暴力改变每个位置的每个字符就行
: 这段的复杂度可以从O(N)降低成O(len(currStr))
| B*******j
发帖数: 232 | 5 谢谢，是的，把每个位置走完26个字母，复杂度就是O（len（str））但是如果在所有
的dict里面找，dict的size很可能远超过每一个word的长度。 |
|
