算法题目-17周-All Paths From Source to Target

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

1、The number of nodes in the graph will be in the range [2, 15].
2、You can print different paths in any order, but you should keep the order of nodes inside one path.

自己解法：目前分析存在最大问题每次都需要重新复制数组，这里消耗太多资源

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ret = new ArrayList();
        List<Integer> Path = new ArrayList();
        Path.add(0);
        findPath(ret,graph,Path,0);
        return ret;
    }
    
    public void findPath(List<List<Integer>> ret,int[][] graph,List<Integer> path,int lastNode){        
        for(int node:graph[lastNode]){
           if(node == graph.length - 1){
               List<Integer> newPath = new ArrayList();
               newPath.addAll(path);
               newPath.add(node);
               ret.add(newPath);
           }else{
               List<Integer> newPath = new ArrayList();
               newPath.addAll(path);
               newPath.add(node);
               findPath(ret,graph,newPath,node);
           }            
        }        
    }  
}

成绩不理想：
Runtime: 3 ms, faster than 50.54% of Java online submissions for All Paths From Source to Target.
Memory Usage: 41.8 MB, less than 73.68% of Java online submissions for All Paths From Source to Target.

官方答案

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        return solve(graph, 0);
    }

    public List<List<Integer>> solve(int[][] graph, int node) {
        int N = graph.length;
        List<List<Integer>> ans = new ArrayList();
        if (node == N - 1) {
            List<Integer> path = new ArrayList();
            path.add(N-1);
            ans.add(path);
            return ans;
        }

        for (int nei: graph[node]) {
            for (List<Integer> path: solve(graph, nei)) {
                path.add(0, node);
                ans.add(path);
            }
        }
        return ans;
    }
}

结果还不如我
Runtime: 6 ms, faster than 20.53% of Java online submissions for All Paths From Source to Target.
Memory Usage: 41.2 MB, less than 85.26% of Java online submissions for All Paths From Source to Target.

目前找到最快解决算法，该算法最大跟自己算法最大优化点，就是重复利用一个List，等找到路径的时候再重新new 一个新List。通过remove方式来实现。

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
                    
        path.add(0);
        dfsSearch(graph, 0, res, path);
                    
        return res;
    }

    private void dfsSearch(int[][] graph, int node, List<List<Integer>> res, List<Integer> path) {
        if (node == graph.length - 1) {
            res.add(new ArrayList<Integer>(path));
            return;
        }

        for (int nextNode : graph[node]) {
            path.add(nextNode);
            dfsSearch(graph, nextNode, res, path);
            path.remove(path.size() - 1);
        }
    }
}