# My java BFS solution

• basically first u construct a graph in which the nodes are the words in dictionary, and two nodes are connected if they are different only by one char.

then we find the min paths from starting word to ending word. this is done using BFS. at each node we trace back to upstream using a list of possible upstream nodes.

``````public class Solution {
List<List<String>> result = new ArrayList<List<String>>();
ArrayList<String> dictionary;
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
ArrayList<String> words = new ArrayList<String>();

dictionary = words;

boolean ok[][] = new boolean[words.size()][words.size()];
for(int i=0;i<words.size();i++) {
for(int j=0;j<words.size();j++) {
if (i==j) ok[i][j] = true;
else
ok[i][j] = findWordsDistance(words.get(i), words.get(j));
}
}

// bfs traversal
int startingIdx = words.indexOf(start);
int endingIdx = words.indexOf(end);

int used[] = new int[words.size()];
ArrayList<Integer> incoming[] = new ArrayList[words.size()];
for(int i=0;i<words.size();i++)
incoming[i] = new ArrayList<Integer>();

used[startingIdx] = 1;
while( q.size() != 0 ) {
Integer startFrom = q.poll();
if (startFrom == endingIdx)
break;
for(int i=0;i<words.size();i++){
if (ok[startFrom][i]) {
if (used[i]==0) {
used[i] = used[startFrom] +1;
}
if (used[startFrom] +1 <= used[i])
}
}
}

// trace back
trace(incoming, startingIdx, endingIdx);

return result;
}

void trace(List<Integer>[] incoming, int start, int end) {
if ( start == end) {
// collect
ArrayList<String> list = new ArrayList<String>();

return;
}

for(int upstream : incoming[end]) {
trace(incoming, start, upstream);
}
}

boolean findWordsDistance(String a, String b) {
if (a.length() != b.length()) return false;
int diff = 0;
for(int i=0;i<a.length();i++) {
if (a.charAt(i) != b.charAt(i)) {
if (++diff >1)
return false;
}
}
return true;
}
}``````

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