# BFS build levels + DFS trace path (Java Solution)

1. use level-order BFS to construct the tree, not using a real tree node structure because leve-order tree structure allows overlapped children nodes.

2. use recursive DFS to trace path according to the level-order tree, not using a stack because recursive require no back trace.

(.)

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

// Build the tree using BFS (level by level)
List<List<String>> gross = new ArrayList<List<String>>();
List<String> first_layer = new ArrayList<String>();
int min = dict.size()+2;
if(dict.contains(start))
dict.remove(start);
if(!dict.contains(end))
while(gross.get(gross.size()-1).size()!=0 && gross.size() < min){
List<String> new_layer = new ArrayList<String>();
for(int i = 0;i < gross.get(gross.size()-1).size();i++){
String s = gross.get(gross.size()-1).get(i);
for(int j = 0;j < s.length();j++){
for(char c = 'a';c <='z';c++){
String t = s.substring(0,j)+c+s.substring(j+1,s.length());
if(t.equals(end)){
if(gross.size()+1 < min)
min = gross.size()+1;
}
if(dict.contains(t)){
dict.remove(t);
}
}
}
}
}

// DFS on the tree to get path
search(new ArrayList<String>(), rlst, gross, 0, 0, end);

return rlst;

}

private void search(List<String> trace, List<List<String>> rlst, List<List<String>> gross, int layer, int index, String end){
List<String> list = new ArrayList<String>(trace);
String s = gross.get(layer).get(index);
if(s.equals(end))
if(layer+1 < gross.size()){
for(int i = 0;i < gross.get(layer+1).size();i++){
if(isNeighbor(s,gross.get(layer+1).get(i)))
search(list, rlst, gross, layer+1,i, end);
}
}
}

private boolean isNeighbor(String a, String b){
if(a.length()!=b.length()){return false;}
int diff = 0;
for(int i = 0;i < a.length();i++)
diff += a.charAt(i)!=b.charAt(i)?1:0;
return diff==1;
}
}``````

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