All Paths From Source To Target


  • 0

    Click here to see the full article post


  • 0
    S

    @awice you can improve the time complexity to 2^N by only appending to the path.
    Solution in short:

    1. Change signature of solve to solve(graph, currentNodeIdx, path, ans)
    2. Run solve like the following from allPathsSourceTarget: solve(graph, 0, [0], [])
    3. Inside solve check that currentNodeIdx == len(graph) - 1, add path to ans then and return
    4. If currentNodeIdx != len(graph) - 1, iterate over graph[currentNodeIdx] and inside the loop append instead of prepending, recurse and then pop back.

  • 0
    L

    I did this using 3 stacks


  • 0
    D

    DFS, Java, 11ms

    class Solution {
        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            int n = graph.length;
            Map<Integer, List<Integer>> g = new HashMap<>();
            
            for (int i = 0; i < n; i++) {
                if (!g.containsKey(i))
                    g.put(i, new ArrayList<>());
                
                for (int j = 0; j < graph[i].length; j++)
                    g.get(i).add(graph[i][j]);
            }
            
            List<List<Integer>> res = new ArrayList<>();
            boolean[] used = new boolean[n];
            List<Integer> path = new ArrayList<>();
            
            path.add(0);
            used[0] = true;
            
            dfs(0, n - 1, used, g, path, res);
            
            return res;
        }
        
        private void dfs(int v, int end, boolean[] used, Map<Integer, List<Integer>> g, List<Integer> path, List<List<Integer>> res) {
            if (v == end) {
                res.add(new ArrayList<>(path));
                return;
            }
            
            List<Integer> next = g.get(v);
            if (next == null)
                return;
            
            for (int x : next) {
                if (!used[x]) {
                    used[x] = true;
                    path.add(x);
                    dfs(x, end, used, g, path, res);
                    path.remove(path.size() - 1);
                    used[x] = false;
                }
            }
        }
    }
    
    

  • 0
    H

    class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    List<List<Integer>> resultList = new ArrayList<>();
    List<Integer> tempList = new ArrayList<>();
    dfs(graph, 0, tempList, resultList);
    return resultList;
    }

    public void dfs(int[][] graph, int start, List<Integer> tempList, List<List<Integer>> resultList) {
        tempList.add(start);
        // 到达终点
        if(start == graph.length - 1) {
            // 加到集合里面
            resultList.add(tempList);
            return;
        }
        // 不存在路径
        if(graph[start].length == 0) {
            return;
        }
        int len = tempList.size();
        for(int i = 0; i < graph[start].length; i ++) {
            // 复制集合,保留现场,便于下一个循环使用
            List<Integer> subList = new ArrayList<>();
    		for (int j = 0; j < len; j++) {
    			subList.add(tempList.get(j));
    		}
            dfs(graph, graph[start][i], subList, resultList);
        }
    }
    

    }


  • 0

    Can you tell me why can there be O(2^N) paths?


Log in to reply
 

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