# two-end BFS runs 33ms with explanation

• one end BFS runs more than 200 ms, it's very slow. Why slow? suppose there have x step to reach the end word from the start word, there would be 26 * 26 * 26 ......* 26 == 26^step.This number is very huge, finally it just find one word in this number of string. It looks like a triangle, the end word in the the last column.

``````
a
b
c
a            .
b            .
s           c             e
.             y
.             .
z            .
z
``````

However, if it goes from start word and end word, let's meet in the middle, the triangle would be shaped like a diamond( 菱形 ), the max length of column would be much shorter than the triangle. The formula is
26^step is much more bigger than 26^(step/2) + 26^(step/2). For example,
step == 6, 26^6 == 308915776 compare to 26^3+26^3 == 35152. It significantly improved the running time performance. Here is my code.

``````    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if(!wordList.contains(endWord)) return 0;
Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
Set<String> dic = new HashSet<>(wordList);
int step = 1;
Set<String> visited = new HashSet<>();
while(!beginSet.isEmpty() &&!endSet.isEmpty()) {
if(beginSet.size() > endSet.size()) {
Set<String> tmp = beginSet;
beginSet = endSet;
endSet = tmp;
}

Set<String> tmp = new HashSet<>();
for(String str : beginSet) {
for(int i = 0; i < str.length(); i++) {
char[] chars = str.toCharArray();
for(char a = 'a'; a <= 'z'; a++) {
chars[i] = a;
String newV = String.valueOf(chars);
if(endSet.contains(newV)) return step+1;
dic.remove(newV);
}
}
}
}
step++;
beginSet = tmp;
}
return 0;
}``````

• great explanation!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.