BFS Solution in Java - 800ms


  • 0
        public static List<List<String>> findLadders(String start, String end, Set<String> dict) {
    		List<List<String>> paths = new ArrayList<List<String>>();
    		dict.add(end);
    		List<String> tovisit = new ArrayList<String>();
    		tovisit.add(start);
    		List<Integer> levels = new ArrayList<Integer>();
    		levels.add(0);
    		Set<String> visited = new HashSet<String>();
    		Map<String,Map<Integer,Set<String>>> prevs = new HashMap<String,Map<Integer,Set<String>>>();
    		prevs.put(start, new HashMap<Integer,Set<String>>());
    		int maxLen = Integer.MAX_VALUE;
    		while(tovisit.size()>0) {
    			String current = tovisit.remove(0);
    			visited.add(current);
    			int level = levels.remove(0);
    			if(level>maxLen) break;
    			if(current.equals(end) && level<maxLen) maxLen=level;
    			else {
    				for(String s: possMoves(current, end, dict, visited)) {
    					if(!tovisit.contains(s)) {
    						tovisit.add(s);
    						levels.add(level+1);
    					}
    					if(!prevs.containsKey(s)) {
    						Map<Integer,Set<String>> levelprevs = new HashMap<Integer,Set<String>>();
    						Set<String> prevset = new HashSet<String>();
    						levelprevs.put(level, prevset);
    						prevs.put(s, levelprevs);
    					}
    					if(prevs.get(s).containsKey(level)) {
    						prevs.get(s).get(level).add(current);
    					}
    				}
    			}
    		}
    		paths = buildPaths(start,end,prevs);
    		return paths;
    	}
    	public static List<List<String>> buildPaths(String start, String end, Map<String,Map<Integer,Set<String>>> prevs) {
    		List<List<String>> paths = new ArrayList<List<String>>();
    		Set<String> prevsteps = null;
    		if(prevs.containsKey(end)) {
    			for(int i:prevs.get(end).keySet()) 
    				prevsteps = prevs.get(end).get(i);
    		}
    		if(prevsteps==null) {
    			if(start.equals(end)) {
    				List<String> path = new ArrayList<String>();
    				path.add(end);
    				paths.add(path);
    			}
    			return paths;
    		}
    		if(prevsteps.size()==0) {
    			System.out.println("prevsteps 0");
    			List<String> path = new ArrayList<String>();
    			path.add(end);
    			paths.add(path);
    		} else {
    			for(String s: prevsteps) {
    				for(List<String> path: buildPaths(start,s,prevs)) {
    					path.add(end);
    					paths.add(path);
    				}
    			}
    		}
    		return paths;
    	}
    	public static List<String> possMoves(String word, String end, Set<String> dict, Set<String> visited) {
    		List<String> moves = new ArrayList<String>();
    		for(int i=0;i<word.length();i++) {
    			char[] chars = word.toCharArray();
    			for(char c = 'a';c<='z';c++) {
    				chars[i] = c;
    				String next = new String(chars);
    				if(dict.contains(next) && !visited.contains(next)) moves.add(next);
    			}
    		}
    		if(moves.contains(end)) {
    			moves = new ArrayList<String>();
    			moves.add(end);
    		}
    		return moves;
    	}

Log in to reply
 

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