[Java] Modified BFS to find 'end' followed by DFS to reconstruct paths


  • 1
    S

    Title gives you my basic idea, there are also comments for you to easier read my code.

    import java.util.LinkedHashMap; 
    
    public class Solution {
        public List<List<String>> findLadders(String start, String end, Set<String> dict) {
            List<List<String>> paths = new ArrayList<>();
            
            // maps String(node) to distance from "start"
            Map<String, Integer> toVisit = new LinkedHashMap<String, Integer>();
            Set<String> discovered = new HashSet<>();
            // maps String(node) to its parents
            Map<String, List<String>> parents = new HashMap<>();
            
            toVisit.put(start, 0);
            discovered.add(start);
            
            int distanceToEnd = -1;
            
            // bfs
            while (!toVisit.isEmpty()) {
                // "removing from queue"
                String tmp = toVisit.entrySet().iterator().next().getKey();
                int distance = toVisit.get(tmp);
                toVisit.remove(tmp);
                
                if (tmp.equals(end)) {
                    distanceToEnd = distance;
                    continue;
                }
                    
                if (distanceToEnd == -1 || distance < distanceToEnd) {
                    // "end" not yet reached OR it was reached but there are other possible shortest
                    // paths to "end"
                    for (String neighbor : neighbors(tmp, dict)) {
                        if (distanceToEnd != -1 && !neighbor.equals(end)) {
                            // "end" was reached but "neighbor" is not "end"
                            continue;
                        }
                        if (!discovered.contains(neighbor)) {
                            // "neighbor" hasn't been disceovered yet
                            discovered.add(neighbor);
                            toVisit.put(neighbor, distance + 1);
                            parents.put(neighbor, new ArrayList<String>());
                            parents.get(neighbor).add(tmp);
                        } else if (toVisit.get(neighbor) != null && toVisit.get(neighbor) == distance + 1) {
                            // "neighbor" has already discovered but "tmp" is also his parent
                            parents.get(neighbor).add(tmp);
                        }
                    }
                }
            }
            
            if (distanceToEnd == -1) {
                return paths;
            }
            
            if (distanceToEnd == 0) {
                paths.add(new ArrayList<String>());
                paths.get(0).add(start);
                return paths;
            }
            
            LinkedList<String> tmpPath = new LinkedList<String>();
            tmpPath.addFirst(end);
            reconstructPaths(end, start, parents, tmpPath, paths);
            return paths;
        }
        
        private void reconstructPaths(String source, String destination, Map<String, List<String>> edges, 
                LinkedList<String> tmpPath, List<List<String>> paths) {
            // dfs
            if (source.equals(destination)) {
                paths.add(new LinkedList<String>(tmpPath));
                return;
            }
            
            for (String neighbor : edges.get(source)) {
                tmpPath.addFirst(neighbor);
                reconstructPaths(neighbor, destination, edges, tmpPath, paths);
                tmpPath.removeFirst();
            }
        }
        
        List<String> neighbors(String s, Set<String> dict) {
            List<String> res = new ArrayList<>();
            char[] chars = s.toCharArray();
            for (int i = 0; i < s.length(); i++) {
                char original = chars[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (original != c) {
                        chars[i] = c;
                        String nei = new String(chars);
                        if (dict.contains(nei)) {
                            res.add(nei);
                        }
                    }
                }
                chars[i] = original;
            }
            return res;
        }
    }

  • 0
    B

    Nice work, but there are some conditions you don't need to check. For ex, when you find the "end", you can just break, because all parents of "end" have already be added. Thus, you don't even to check distanceToEnd,
    if (tmp.equals(end)) {
    distanceToEnd = distance;
    break;
    }

            for (String neighbor : neighbors(tmp, dict)) {
                if (!discovered.contains(neighbor)) {
                        // "neighbor" hasn't been disceovered yet
                    discovered.add(neighbor);
                    toVisit.put(neighbor, distance + 1);
                    parents.put(neighbor, new ArrayList<String>());
                    parents.get(neighbor).add(tmp);
                } else if (toVisit.get(neighbor) != null && toVisit.get(neighbor) == distance + 1) {
                        // "neighbor" has already discovered but "tmp" is also his parent
                    parents.get(neighbor).add(tmp);
                }
            }
    

    already done the work.


Log in to reply
 

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