Leetcode 332: Reconstruct Itinerary

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:

1. 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"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.
4. One must use all the tickets once and only once.

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.

Problem Analysis:

For the description mentioned it has at least one valid solution, so we can construct the itineraries using dfs (depth first search) algorithm. Because there may be multiple valid itineraries, we should construct with smallest lexical order.

Note that don’t worry about loops or repeated airports, as problem description tips that it has valid solution, so dfs algorithm can succeed to construct it no matter whether it has loops or not.

Solution:

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (const auto& array: tickets)
            store_[array.front()].insert(array.back());
        
        string current{"JFK"};
        helper(current);
        reverse(result_.begin(), result_.end());
        
        return result_;
    }
    
    void helper(const string& current) {
        while (store_[current].size() > 0) {
            string next = *store_[current].begin();
            store_[current].erase(store_[current].begin());
            helper(next);
        }        
        
        result_.push_back(current);
    }
    
private:
    unordered_map<string, multiset<string>> store_;
    vector<string> result_;
};

Time Complexity: O(n)

Space Complexity: O(n)