From backtracking to SSSP and to DP

Fix Flight Itinerary

A naive backtracking algorithm will get TLE

int dis(string a, string b){
    int ret = 0;
    for (int i = 0; i < a.size(); ++i){
        ret += a[i] != b[i];
    }
    return ret;
}
void backtrack(int i,string airport, vector<string>& itinerary,unordered_map<string, vector<string>> & graphs, int &ret, int curr){
    if (i == itinerary.size()){
        ret = min(ret, curr);
        return;
    }
    for (auto & neighbor: graphs[airport]){
        curr += dis(neighbor, itinerary[i]);
        backtrack(i + 1, neighbor, itinerary, graphs, ret, curr);
        curr -= dis(neighbor, itinerary[i]);
    }
}
int solve(vector<string>& itinerary, vector<vector<string>>& edges) {
    unordered_set<string> airports;
    unordered_map<string, vector<string>> graphs;
    for (auto &e: edges){
        auto u = e[0], v = e[1];
        airports.insert(u); airports.insert(v);
        graphs[u].push_back(v);
    }
    //cout << airports.size() << endl;
    for (auto airport: airports) graphs["root"].push_back(airport);
    int ret = INT_MAX;
    backtrack(0, "root", itinerary, graphs, ret, 0);
    return ret;
    
}

We can also try to solve it by using BFS approach to naively update the result level by level. Here the idea is we have n iterations and m airports, initially, we have i = 0 and j from 0 to m -1. The previous cost is 0.

We put those nodes into a queue and update the cost by using a BFS approach. However, this solution will get TLE as the time complexity of this one is pretty high (you may update the graph multiple times)

typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
int dis(string a, string b){
    int ret = 0;
    for (int i = 0; i < a.size(); ++i){
        ret += a[i] != b[i];
    }
    return ret;
}
int solve(vector<string>& itinerary, vector<vector<string>>& edges) {
    unordered_set<string> airport_sets;
    unordered_map<string, vector<string>> graphs;
    for (auto &e: edges){
        auto u = e[0], v = e[1];
        airport_sets.insert(u); airport_sets.insert(v);
        graphs[u].push_back(v);
    }
    vector<string>airports(airport_sets.begin(), airport_sets.end());
    unordered_map<string, int> airport_idx;
    
    const int n = itinerary.size(), m = airports.size();
    for (int j = 0; j < m; ++j){
        airport_idx[airports[j]] = j;
    }
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));
    queue<pair<PII, int>> Q;
    for (int j = 0; j < m; ++j){
        Q.emplace(make_pair(0, j), 0);
    }
    int ret = INF;
    while (!Q.empty()){
        auto [ij, cost] = Q.front(); Q.pop();
        auto [i, j] = ij;
        dp[i][j] = min(dp[i][j], cost + dis(itinerary[i], airports[j]));
        if (i == n - 1) {
            ret = min(ret, dp[i][j]);
            continue;
        }
        for (auto v: graphs[airports[j]]){
            int newj = airport_idx[v];
            Q.emplace(make_pair(i + 1, newj),dp[i][j]);
        }
    }
    return ret;
    
}

Then I realize this problem is very similar to this problem and we can solve it by using SSSP algorithm such as Dijkstra’s algorithm.

typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
int compute_edge_cost(string a, string b){
    int ret = 0;
    for (int i = 0; i < a.size(); ++i){
        ret += a[i] != b[i];
    }
    return ret;
}
int solve(vector<string>& itinerary, vector<vector<string>>& edges) {
    unordered_set<string> airport_sets;
    unordered_map<string, vector<string>> graphs;
    for (auto &e: edges){
        auto u = e[0], v = e[1];
        airport_sets.insert(u); airport_sets.insert(v);
        graphs[u].push_back(v);
    }
    vector<string>airports(airport_sets.begin(), airport_sets.end());
    unordered_map<string, int> airport_idx;
    
    const int n = itinerary.size(), m = airports.size();
    for (int i = 0; i < m; ++i){
        airport_idx[airports[i]] = i;
    }
    vector<vector<int>> dis(m + 1, vector<int>(n + 1, INF));
    priority_queue<pair<int, PII>, vector<pair<int, PII>>, greater<pair<int, PII>> > PQ;
    for (int i = 0; i < m; ++i){
        int thiscost = compute_edge_cost(airports[i], itinerary[0]);
        PQ.emplace(thiscost, make_pair(i, 0));
        dis[i][0] = thiscost;
    }
    
    while (!PQ.empty()){
        auto [cost, ij] = PQ.top(); PQ.pop();
        auto [i, j] = ij;
        // lazy deletion
        if (cost > dis[i][j]) continue;
        if (j >= n - 1) continue;
        for (auto v: graphs[airports[i]]){
            int newi = airport_idx[v];
            auto newcost = dis[i][j] + compute_edge_cost(airports[newi], itinerary[j+1]);   
            if (newcost < dis[newi][j + 1]){
                // 1) update dis
                // 2) delete the old one in the pq by using lazy deletion
                dis[newi][j+1] = newcost;
                // 3) put the new status in PQ
                PQ.emplace(newcost, make_pair(newi, j + 1));
            }  
        }
    }
    int ret = INF;
    for (int i = 0; i < m; ++i)ret = min(ret, dis[i][n-1]);
    return ret;
    
}

DP

We can use DP to solve this problem. The trick is look backward. Stand from airportA at the ith itinerary, check all the previous airports which can arrive airportA, then the new values will be previous value of previous airport + the distance of the airportA to itinerary[i].

const int INF = 0x3f3f3f3f;
int dis(string a, string b){
    int ret = 0;
    for (int i = 0; i < a.size(); ++i) ret += a[i] != b[i];
    return ret;
}
int solve(vector<string>& itinerary, vector<vector<string>>& edges) {
    unordered_map<string, vector<string>> graphs_dst_src;
    unordered_set<string> airport_set;
    for (auto &e: edges){
        auto u = e[0], v = e[1];
        graphs_dst_src[v].push_back(u);
        airport_set.insert(u); airport_set.insert(v);
    }
    vector<string> airports(airport_set.begin(), airport_set.end());
    const int m = airports.size();
    unordered_map<string, int> airport_idx;
    vector<int> dp(m, INF);
    for (int j = 0; j < m; ++j){
        airport_idx[airports[j]] = j;
        dp[j] = dis(itinerary[0], airports[j]);
    }
    const int n = itinerary.size();
    for (int i = 1; i < n; ++i){
        vector<int> newdp(m, INF);
        for (int j = 0; j < m; ++j){
            int thiscost = dis(airports[j], itinerary[i]);
             for (auto prev: graphs_dst_src[airports[j]]){
                 newdp[j] = min(newdp[j], dp[airport_idx[prev]] + thiscost);
             }
        }
        dp = newdp;
    }
    int ret = INF;
    for (int j = 0; j < m; ++j) ret = min(ret, dp[j]);
    return ret;
    
}