reconstruct-itinerary.go

// https://leetcode.com/problems/reconstruct-itinerary
// MUC -> [LHR]
// JFK -> [MUC]
// SFO -> [SJC]
// LHR -> [SFO]

//
// JFK -> [SFO, ATL]
// SFO -> [ATL]
// ATL -> [JFK,SFO]
//
// JFK, ATL, JFK, SFO, ATL, SFO
// JFK, SFO, ATL, JFK, ATL, SFO

import "sort"

func findItinerary(tickets [][]string) []string {
    graph := make(map[string][]string)
    visited := make(map[string]bool)
    
    for _, pair := range tickets {
        from, to := pair[0], pair[1]
        graph[from] = append(graph[from], to)
    }
    
    for _, list := range graph {
        sort.Strings(list)
    }
    
    return dfs(graph, "JFK", visited, []string{}, len(tickets))
}

func dfs(
    graph map[string][]string,
    root string,
    visited map[string]bool,
    path []string,
    flights int,
) []string {
    if len(path) == flights {
        return append(path, root)
    }
    
    for i, child := range graph[root] {
        key := fmt.Sprintf("%s_%s_%d", root, child, i)
        
        if visited[key] {
            continue
        }
        
        visited[key] = true
        result := dfs(graph, child, visited, append(path, root), flights)
        visited[key] = false
        
        if result != nil {
            return result
        }
    }
    
    return nil
}