Version I - BFS
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
HashSet<String> words = new HashSet<>(wordList);
Queue<String> queue = new LinkedList<>();
int level = 0;
queue.offer(beginWord);
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int i = 0; i < size; ++i) {
String word = queue.poll();
if (word.equals(endWord)) return level;
char[] chars = word.toCharArray();
for (int j = 0; j < chars.length; ++j) {
char c = chars[j];
for (char k = 'a'; k <= 'z'; ++k) {
chars[j] = k;
if (words.contains(String.valueOf(chars))) {
queue.offer(String.valueOf(chars));
words.remove(String.valueOf(chars));
}
}
chars[j] = c;
}
}
}
return 0;
}
}
Version II - two-end BFS
dont' forget the case when end word is not in the word list
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
HashSet<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
HashSet<String> beginSet = new HashSet<>();
HashSet<String> endSet = new HashSet<>();
beginSet.add(beginWord);
endSet.add(endWord);
int level = 1;
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
if (beginSet.size() > endSet.size()) {
HashSet<String> set = beginSet;
beginSet = endSet;
endSet = set;
}
HashSet<String> tmpSet = new HashSet<>();
for (String word : beginSet) {
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; ++i) {
char c = chars[i];
for (char j = 'a'; j <= 'z'; ++j) {
chars[i] = j;
String str = String.valueOf(chars);
if (endSet.contains(str)) {
return level + 1;
}
if (words.contains(str)) {
words.remove(str);
tmpSet.add(str);
}
}
chars[i] = c;
}
}
level++;
beginSet = tmpSet;
}
return 0;
}
}