# 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. 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.

# Solution

Approach 1: DFS.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

class Solution {
private:
    unordered_map<string,vector<string>> links;
    vector<string> res;
    bool findRes;
    int total;
    int cmp(string a, string b) {
        for (int i = 0; i < a.size(); ++i)
        {
            if (a[i] > b[i])
                return 1;
            else if (a[i] < b[i])
                return -1;
        }
        return 0;
    }
    void doFindItinerary(string start, vector<string>& path) {
        path.push_back(start);
        total--;
        if (total == 0)
        {
            res = path;
            findRes = true;
        }
        else
        {
            for (vector<string>::iterator it = links[start].begin();
                 it != links[start].end(); ++it)
            {
                string next = *it;
                links[start].erase(it);
                doFindItinerary(next, path);
                links[start].insert(it, next);
                if (findRes)
                    break;
            }
        }
        path.pop_back();
        total++;
    }
    void doFindItinerary(string start) {
        while (links[start].size() > 0)
        {
            string next = links[start][0];
            links[start].erase(links[start].begin());
            doFindItinerary(next);
        }
        res.push_back(start); // Need to be here instead of before while().
    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        findRes = false;
        total = tickets.size() + 1;
        for (int i = 0; i < tickets.size(); ++i)
        {
            string start = tickets[i][0];
            string end = tickets[i][1];
            vector<string>::iterator it = links[start].begin();
            for (; it != links[start].end(); ++it)
            {
                if (cmp(*it, end) > 0)
                    break;
            }
            links[start].insert(it, end);
        }
        
        //vector<string> path;
        //doFindItinerary("JFK", path);
        
        doFindItinerary("JFK");
        std::reverse(res.begin(), res.end());
        
        return res;
    }
};