LeetCode 797. All Paths From Source to Target in F#
URL
https://leetcode.com/problems/all-paths-from-source-to-target/description/
Code
https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/problems/0797/main.fsx
let allPathsSourceTarget (graph: int list []) : int list list =
let target = graph.Length - 1
let rec allPathsSourceTarget' q target (graph: int list []) acc =
match q with
| [] -> acc
| (node, path, visited) :: t ->
if node = target then
allPathsSourceTarget' t target graph ((path |> List.rev) :: acc)
else
let visited' = Set.add node visited
let q' =
graph.[node]
|> List.fold
(fun acc n ->
if Seq.contains n visited' then
acc
else
(n, (n :: path), visited') :: acc)
t
allPathsSourceTarget' q' target graph acc
let q = [ (0, [ 0 ], Set.empty) ]
allPathsSourceTarget' q target graph []