[Swift]LeetCode797.所有可能的路径|AllPathsFromSourcetoTarget

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10547365.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）

二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了a→b你就不能从b→a）空就是没有下一个结点了。

示例:
输入: [[1,2], [3], [3], []] 
输出: [[0,1,3],[0,2,3]] 
解释: 图是这样的:
0--->1
|    |
v    v
2--->3
这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3.

提示:

结点的数量会在范围 [2, 15] 内。
你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。

84ms

 1 class Solution {
 2     func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
 3         
 4         var result : [[Int]] = []
 5         addPath([0], from: graph, graph, &result)
 6     
 7         return result
 8     }
 9     func addPath(_ current : [Int] , from graph: [[Int]] , _ oriGraph:[[Int]], _ store:inout [[Int]]) {
10         
11         if graph.count == 0 || graph[0].count == 0{
12             store.append(current)
13             return
14         }
15         
16         for g in graph[0] {
17             addPath(current + [g], from: Array(oriGraph[g..<oriGraph.count]), oriGraph, &store)
18         }
19     }
20 }

132ms

 1 class Solution {
 2     private var cache = [Int:[[Int]]]()
 3     private var length = 0
 4     
 5     func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
 6         var graph = graph; length = graph.count - 1
 7         cache[length] = [[Int]]()
 8         defer {
 9             cache = [Int:[[Int]]]()
10         }
11         return middleTarget(0,&graph)
12     }
13     
14     private func middleTarget(_ start: Int, _ graph: inout [[Int]]) -> [[Int]] {
15         if (cache[start] == nil) {
16             var tmpAns = [[Int]]()
17             for next in graph[start] {
18                 if (next == length) {
19                     tmpAns.append([start,next])
20                 } else {
21                     for path in middleTarget(next,&graph) {
22                         tmpAns.append([start]+path)
23                     }
24                 }
25             }
26             cache[start] = tmpAns
27         }
28         return cache[start]!
29     }
30 }

140ms

 1 class Solution {
 2     func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
 3         var solution = [[Int]]()
 4         
 5         var working = [[0]]
 6         while !working.isEmpty {
 7             // Push all working paths one node deeper
 8             working = helper(graph: graph, working: working)
 9             
10             // These have hit the end so add to solution
11             let workingSolutions = working.filter { $0.last == graph.count - 1 }
12             solution.append(contentsOf: workingSolutions)
13             
14             // These haven't reached the end yet
15             working = working.filter { $0.last != graph.count - 1 }
16         }
17         
18         return solution
19     }
20     
21     /// Push all paths forward one node
22     /// Prune all paths that are dead ends/ don't lead to last node
23     func helper(graph: [[Int]], working: [[Int]]) -> [[Int]] {
24         var newWorking = [[Int]]()
25         
26         for w in working {
27             guard let currentNode = w.last,
28                 currentNode < graph.count else {
29                 continue
30             }
31             
32             let nextNodes = graph[currentNode]
33             guard !nextNodes.isEmpty else {
34                 continue
35             }
36             
37             for node in nextNodes {
38                 var newPath = w
39                 newPath.append(node)
40                 
41                 newWorking.append(newPath)
42             }
43         }
44         
45         return newWorking
46     }
47 }

144ms

 1 class Solution {
 2     func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
 3     var array: [[Int]] = []
 4     var path = [0]
 5     findPath(with: graph, index: 0, result: &array, path: &path)
 6     return array
 7 }
 8 
 9 func findPath(with graph:[[Int]], index: Int, result: inout [[Int]], path: inout [Int]) {
10     guard index != graph.count - 1 else {
11         result.append(path)
12         return
13     }
14     for i in graph[index] {
15         var tempPath = path + [i]
16         findPath(with: graph, index: i, result: &result, path: &tempPath)
17     }
18   }
19 }

156ms

 1 class Solution {
 2     func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {    
 3         return nextPosition(graph, visited:[0])
 4     }
 5 
 6     func nextPosition(_ graph:[[Int]], visited:[Int]) -> [[Int]] {
 7         var results = [[Int]]()
 8         var latestPosition = visited.last!
 9         if latestPosition == graph.count - 1 {
10             results.append(visited)
11         } else {
12             for position in graph[visited.last!] {
13                 if visited.contains(position) {
14                     continue
15                 } else {
16                     var visited_new = visited
17                     visited_new.append(position)
18                     results += nextPosition(graph, visited: visited_new)
19                 }
20             }
21         }
22         return results
23     }
24 }

164ms

 1 class Solution {   
 2     func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
 3         var results = [[Int]]()
 4         search(graph.count - 1, [0], 0, graph, &results)
 5         return results
 6     }
 7     
 8      func search(_ target: Int,
 9                 _ path: [Int], 
10                 _ currentNode: Int, 
11                 _ graph: [[Int]], 
12                 _ results: inout [[Int]]) {
13         if currentNode == target {
14             results.append(path)
15             return
16         }
17         for nextNode in graph[currentNode] {
18                 search(target, 
19                    path + [nextNode], 
20                    nextNode, graph, 
21                    &results)
22         }
23     }
24 }

Runtime: 168 ms

Memory Usage: 20.7 MB

 1 class Solution {
 2     func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
 3         var graph = graph
 4         return helper(&graph, 0)
 5     }
 6     
 7     func helper(_ graph:inout [[Int]],_ cur:Int) -> [[Int]]
 8     {
 9         if cur == graph.count - 1
10         {
11             return [[graph.count - 1]]
12         }
13         var res:[[Int]] = [[Int]]()
14         for neigh in graph[cur]
15         {
16             var arr:[[Int]] = helper(&graph, neigh)
17             for i in 0..<arr.count
18             {
19                 var path:[Int] = arr[i]
20                 path.insert(cur,at:0);
21                 res.append(path);
22             }                
23         }
24         return res
25     }
26 }

208ms

 1 class Solution {
 2     func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
 3         return dfs(0, graph)
 4     }
 5     
 6     private func dfs(_ node: Int, _ graph: [[Int]]) -> [[Int]] {
 7         var result = [[Int]]()
 8         if node == (graph.count - 1) {
 9             return [[node]]
10         }
11         
12         for edge in graph[node] {
13             let solutions = dfs(edge, graph)
14             for sol in solutions {
15                 result.append([node] + sol)
16             }
17         }
18         return result
19     }
20 }