问个经典题目，感觉没错啊，可是过不了OJ，超时了，请大神帮着# JobHunting - 待字闺中
B*j
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;
}
}
}
}
过了
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
// write your code here
int len = dict.size();
if(len < 1){
return 0;
}
Queue
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;
}
}
}
}
