URL

Reconstruct Itinerary - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0332/main.fsx

let toGraphAndTicketCount (tickets: (string * string) list) : Map<string, string list> * Map<(string * string), int> =
    let rec toGraph' tickets graph ticketCount =
        match tickets with
        | [] -> graph, ticketCount
        | (departure, arrival) :: t ->
            let graph' =
                match Map.tryFind departure graph with
                | Some(v) -> Map.add departure (arrival :: v) graph
                | None -> Map.add departure [ arrival ] graph

            let ticketCount' =
                match Map.tryFind (departure, arrival) ticketCount with
                | Some(v) -> Map.add (departure, arrival) (v + 1) ticketCount
                | None -> Map.add (departure, arrival) 1 ticketCount

            toGraph' t graph' ticketCount'

    toGraph' tickets Map.empty Map.empty

let findItinerary (tickets: (string * string) list) : string list =
    let rec findItinerary' departure visited used limit graph ticketCount =
        if used = limit then
            Some(List.rev visited)
        else
            match Map.tryFind departure graph with
            | None -> None
            | Some(arrivals) ->
                arrivals
                |> List.fold
                    (fun acc arrival ->
                        match acc with
                        | Some(_) -> acc
                        | None ->
                            let key = departure, arrival

                            match Map.tryFind key ticketCount with
                            | None -> None
                            | Some(v) ->
                                if v > 0 then
                                    let ticketCount' = Map.add key (v - 1) ticketCount
                                    findItinerary' arrival (arrival :: visited) (used + 1) limit graph ticketCount'
                                else
                                    None)
                    None

    let graph, ticketCount = toGraphAndTicketCount tickets
    let graph' = Map.map (fun _ v -> List.sort v) graph
    let limit = List.length tickets

    match findItinerary' "JFK" [ "JFK" ] 0 limit graph' ticketCount with
    | Some(v) -> v
    | None -> failwith "never reach here"