BFS build levels + DFS trace path (Java Solution)


  • 0
    S
    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;
                    first_layer.add(start);
                    gross.add(first_layer);
                    if(dict.contains(start))
                        dict.remove(start);
                    if(!dict.contains(end))
                    	dict.add(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);
                                        new_layer.add(t);
                                    }
                                }
                            }
                        }
                        gross.add(new_layer);
                    }
                    
                    // 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);
                    list.add(s);
                    if(s.equals(end))
                        rlst.add(list);
                    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;
            	}
            }

Log in to reply
 

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