Daily LeetCode 797. All Paths From Source to Target

https://leetcode.com/problems/all-paths-from-source-to-target/

Medium

问题描述：

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.

题目分析：

这一题给定了有向无环图graph，要求找出所有起点到终点的路径。

这一题图的表示方法有点奇怪，给定二维数组graph，graph[i]的内容表示结点i指向哪些结点，例如题中例子：graph[0]=[1, 2]表明结点0分别有指向1， 2两个结点的路径。

我们直接套用经典的dfs模板就能够解决这一题，遍历停止的条件是当前位置等于终点。

代码：

class Solution(object):
    def allPathsSourceTarget(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """

        def dfs(graph, res, position, path):
            if position == len(graph) - 1:
                res.append(path)
                return

            else:
                for n in graph[position]:
                    dfs(graph, res, n, path + [n])

        res = []
        dfs(graph, res, 0, [0])

        return res