LeetCode 797. All Paths From Source to Target

Posted on | In |
Words count in article: 192 | Reading time ≈ 1

题目

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.

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

思路

DFS.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def allPathsSourceTarget(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(graph, 0, len(graph)-1, res, [0])
        return res
    
    
    def dfs(self, graph, start, end, res, path):
        if start == end:
            res.append(path)
        else:
            for n in graph[start]:
                self.dfs(graph, n, end, res, path+[n])