BFS solution need to be improved


  • 0
    A

    The basic idea here is to build the graph by BFS and at the same time record all the paths to endWord. When we are building the graph, if we reach endWord at a level(Will compute all the node of this level and then quit), it's time to end building graph.

    The code now runs in 170ms and I want to know if there are some ways to make it faster.

    Thanks,

    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
    	HashMap<String, List<List<String>>> pathes = new HashMap<>();
    	List<List<String>> allPath = new ArrayList<>();
    	List<String> path = new ArrayList<>();
    	path.add(beginWord);
    	allPath.add(path);
    	pathes.put(beginWord, allPath);
    	wordList.add(endWord);
    	return buildGraph(beginWord, endWord, wordList, pathes);
    }
    public List<List<String>> buildGraph(String beginWord, String endWord, Set<String> wordList,
    		HashMap<String, List<List<String>>> paths) {
    	List<String> level = new ArrayList<>();
    	HashSet<String> inGraph = new HashSet<>();
    	level.add(beginWord);
    	inGraph.add(beginWord);
    	boolean find = false;
    	while (!level.isEmpty()) {
    		List<String> parent = level;
    		level = new ArrayList<>();
    		for (String s : parent) {
    			char[] sh = s.toCharArray();
    			List<List<String>> onePath = paths.get(s);
    			for (int i = 0; i < sh.length; ++i) {
    				char c = sh[i];
    				for (char ch = 'a'; ch <= 'z'; ++ch) {
    					sh[i] = ch;
    					String temp = String.valueOf(sh);
    					if (temp.equals(endWord)) {
    						find = true;
    					}
    					if (wordList.contains(temp) && (!inGraph.contains(temp))) {
    						List<List<String>> tempPath = new ArrayList<>();
    						for(List<String> l : onePath){
    							List<String> p = new ArrayList<>(l);
    							p.add(temp);
    							tempPath.add(p);
    						}
    						if(paths.containsKey(temp)){
    							List<List<String>> ll = paths.get(temp);
    							for(List<String> l : tempPath){
    								ll.add(l);
    							}
    						}else{
    							paths.put(temp, tempPath);
    							level.add(temp);
    						}
    					}
    				}
    				sh[i] = c;
    			}
    		}
    		if (find) {
    			return paths.get(endWord);
    		}
    		inGraph.addAll(level);
    	}
    	return new ArrayList<>();
    }

Log in to reply
 

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