[LeetCode] Challenge log 797

Posted on |
797. All Paths From Source to Target
  1. Basic DFS problem.
  2. Caching may accerlerate the time, but I did not try~

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.
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def allPathsSourceTarget(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """
        allPaths = []
        self.printPaths([0], graph, allPaths)
        return allPaths
        
    def printPaths(self, path, graph, allPaths):
        if len(graph[path[-1]]) != 0: 
            for i in graph[path[-1]]:
                if i == len(graph) - 1:
                    allPaths.append(path[:] + [i])
                else:
                    self.printPaths(path[:] + [i], graph, allPaths)
0%