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:

• 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:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Backtracking Solution

class Solution {
public:
    vector<string> compare(vector<string> v1, vector<string> v2) {
        int n1 = v1.size(), n2 = v2.size();
        if ( n1 > n2 ) return v1;
        if ( n2 > n1 ) return v2;
        for ( int i = n1-1; i >=0; i-- ) {
            for ( int j = 0; j <= 2; j++ ) {
                if ( v1[i][j] < v2[i][j] ) return v1;
                if ( v1[i][j] > v2[i][j] ) return v2;
            }
        }
        return v1;
    }
    vector<string> fromCity(vector<pair<string, string>> tickets, vector<bool> available, string city) {
        int n = tickets.size();
        vector<vector<string>> res;
        for ( int i = 0; i <= n-1; i++ ) {
            if ( tickets[i].first != city or ( not available[i]) ) continue;
            auto available_copy = available;
            available_copy[i] = false;
            vector<string> tmp_res = fromCity(tickets, available_copy, tickets[i].second);
            tmp_res.push_back(city);
            res.push_back(tmp_res);
        }
        int nres = res.size();
        if ( nres == 0 ) {vector<string> tmp(1, city); return tmp;}
        if ( nres == 1 ) return res[0];
        vector<string> tmp = res[0];
        for ( int i = 1; i <= nres-1; i++ ) tmp = compare(tmp, res[i]);
        return tmp;
    }
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        int n = tickets.size();
        vector<bool> available(n, true);
        vector<string> res = fromCity(tickets, available, "JFK");
        reverse(res.begin(), res.end());
        return res;
    }
};

DFS Solution

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        unordered_map<string, vector<string>> record;
        int n = tickets.size();
        for ( int i = 0; i <= n-1; i++ ) {
            string s1 = tickets[i].first, s2 = tickets[i].second;
            if ( record.find(s1) == record.end() ) {
                vector<string> tmp(1, s2);
                record[s1] = tmp;
            }
            else record[s1].push_back(s2);
        }
        for (auto it = record.begin(); it != record.end(); it++ ) sort(it->second.begin(), it->second.end());
        stack<string> s;
        vector<string> res;
        s.push("JFK");
        while ( ! s.empty() ) {
            string city = s.top();
            if ( record.find(city) == record.end() or record[city].size() == 0 ) {
                res.push_back(city);
                s.pop();
            }
            else {
                s.push(record[city][0]);
                record[city].erase(record[city].begin());
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};