LeetCode: Reconstruct Itinerary

Posted on August 21, 2019July 26, 2020 by braindenny

Reconstruct Itinerary

Similar Problems:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.

Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/reconstruct-itinerary
// Basic Ideas: dfs
//  Notice:
//    To avoid loop, edge can't be used twice
//    There might be duplicate tickets
//
// Complexity: Time ? Space ?
import "sort"
func dfs(node string, m map[string][]string, visited map[string][]bool, res *[]string, count int) bool {
    if len(*res) == count { return true }
    for i, node2 := range m[node] {
        if !visited[node][i] {
            visited[node][i] = true
            *res = append(*res, node2)
            if dfs(node2, m, visited, res, count) {
                return true
            }
            *res = (*res)[0:len(*res)-1]
            visited[node][i] = false
        }
    }
    return false
}

func findItinerary(tickets [][]string) []string {
    m := map[string][]string{}
    visited := map[string][]bool{}
    for _, ticket := range tickets{
        from, to := ticket[0], ticket[1]
        m[from] = append(m[from], to)
    }
    for key, _ := range m {
        sort.Slice(m[key], func(i, j int) bool {
            return m[key][i]<m[key][j]
        })
        visited[key] = make([]bool, len(m[key]))
    }
    res := []string{"JFK"}
    dfs("JFK", m, visited, &res, len(tickets)+1)
    return res
}

Post Views: 0