# Two end BFS java solution, 26ms beat 99.62%

• ``````    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (wordList == null || wordList.size() == 0) return 0;
Set<String> dic = new HashSet<>(wordList);
if (!dic.contains(endWord)) return 0;
if (beginWord.equals(endWord)) return 1;
Set<String> q1 = new HashSet<>(), q2 = new HashSet<>();
dic.remove(beginWord);
dic.remove(endWord);
return twoEndBFS(q1, q2, dic, 2);
}

private int twoEndBFS(Set<String> q1, Set<String> q2, Set<String> dic, int len) {
if (q1.isEmpty() || q2.isEmpty()) return 0;
if (q1.size() > q2.size()) return twoEndBFS(q2, q1, dic, len);

Set<String> temp = new HashSet<>();
for (String word : q1) {
char[] chArr = word.toCharArray();
for (int i = 0; i < chArr.length; ++i) {
char c = chArr[i];
for (char newC = 'a'; newC <= 'z'; ++newC) {
chArr[i] = newC;
String next = new String(chArr);
if (q2.contains(next)) return len;
if (dic.contains(next)) {
dic.remove(next);
}
}
chArr[i] = c;
}
}
return twoEndBFS(temp, q2, dic, len + 1);
}
``````

• Why do you store the wordList from an ArrayList to a Set in dic?

Why can't you use the ArrayList wordList itself when removing and comparing elements?

• @deepak_um The reason is that HashSet.contains() has O(1) time complexity, while checking in ArrayList costs O(n), where n is the length of the ArrayList.

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