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:
- The number of nodes in the graph will be in the range
[2, 15]
. - You can print different paths in any order, but you should keep the order of nodes inside one path.
分析:题目要求找从0位置到N-1位置能走的所有路径。根据题目意思也很容易想到用DFS做。
DFS是真的难,有的DFS调用之后需要返回原位置,比如这个题目,调用一次DFS之后就要回退回上一个状态。比如全排列问题。但是有的DFS就不需用,比如树里面的很多DFS。但是树里面又有很多需用,很烦。真的菜。。。
这个题目的代码总体还是比较简单的,我的思路是在递归里用一个cur指针指示当前位置,遍历每个graph[cur],找他的下一个。代码如下:
1 class Solution { 2 List<List<Integer>> res = new ArrayList<>(); 3 List<Integer> path = new ArrayList<>(); 4 public List<List<Integer>> allPathsSourceTarget(int[][] graph) { 5 path.add(0); 6 helper(0,graph); 7 return res; 8 } 9 private void helper(int cur, int[][] graph) { 10 if ( cur == graph.length - 1 ){ 11 res.add(new ArrayList<>(path)); 12 return; 13 } 14 else { 15 for ( int node : graph[cur] ){ 16 path.add(node); 17 helper(node,graph); 18 path.remove(path.size()-1); 19 } 20 } 21 } 22 }
运行时间4ms,击败99.89%提交。
这里严重注意11行。刚开始我是用res.add(path),发现结果是全[0],分析了一下,因为18行有个回退,所以如果不这样做的话,最后path都会被删除成0。