# Clean and easy Java solution for Word Ladder problem (Two-side BFS)

• I've tried DFS and one-directional BFS and both of them were giving me time limit error. Then I decided to go with two-side BFS, and it was still timing out. Then I realized the problem was that I was trying to build the whole graph at the beginning, which was time consuming. All of this led me for more dynamic approach of generating new words, apparently it was 5 times faster than pre-building the whole graph.

Coloring is used for "intersecting the circles": one starts from beginWord, second from endWord. At the moment they intersect we stop and count the distance for both, and the sum is result.

``````class Solution {
Map<String, Integer> wordDepth;
Map<String, Integer> colors;
Set<String> words;
Set<String> used;

int minDepth;
int dictSize;
String endWord;
String beginWord;
boolean found = false;

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord))
return 0;

this.minDepth = Integer.MAX_VALUE;
this.dictSize = wordList.size();
this.beginWord = beginWord;
this.endWord = endWord;

used = new HashSet();
words = new HashSet();
colors = new HashMap();
wordDepth = new HashMap();

for (int i = 0; i < wordList.size(); i++)
if (!wordList.get(i).equals(beginWord))

colors.put(beginWord, 0);
colors.put(endWord, 1);

bfsTwoSide(beginWord, endWord);

return found ? this.minDepth : 0;
}

public void bfsTwoSide(String beginWord, String endWord) {
wordDepth.put(beginWord, 1);
wordDepth.put(endWord, 1);

String[] q = new String[dictSize + 1];
int left = 0;
int right = 1;

q[left] = beginWord;
q[right] = endWord;

while (left <= right && !found) {
char[] curWord = q[left].toCharArray();
String curWordStr = String.valueOf(curWord);

for (int i = 0; i < curWord.length; i++) {
char old = curWord[i];
for (char c = 'a'; c <= 'z'; c++) {
curWord[i] = c;
String newWord = String.valueOf(curWord);

if (words.contains(newWord)) {
if (!used.contains(newWord)) {
right++;
q[right] = newWord;
colors.put(newWord, colors.get(curWordStr));
wordDepth.put(newWord, wordDepth.get(curWordStr) + 1);
} else if (colors.get(curWordStr) != colors.get(newWord)) {
this.minDepth = wordDepth.get(curWordStr) + wordDepth.get(newWord);
found = true;
return;
}
}
}

curWord[i] = old;
}

left++;
}
}
}
``````

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