797 All Paths From Source to Target

Posted on | In

All Paths From Source to Target

1
2
3
4
5
6
7
8
9
10
11
12
13
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.

直接从0节点，DFS找到N-1就行了。因为是无环图也不需要判断有没有遍历过。

在找的时候会有重复的节点被找多次，可以采用Map<Integer,List<List> 来存储已经遍历过的节点。但提交的时候时间更长了，估计测试样例中没有多个节点重复找的情况比较少。

这种会重复路径的问题，类似DP，要记得试着去记录下来