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:

// Blog link: 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 }