Fix Flight Itinerary - Google Top Interview Questions

                        Solution in C++ :

int solve(vector<string>& arr, vector<vector<string>>& edge) {
    int n = arr.size();
    int m = edge.size();
    set<string> st;
    for (auto it : edge) {
        st.insert(it[0]);
        st.insert(it[1]);
    }

    map<string, int> mp;
    vector<string> str;
    int cnt = 0;
    for (string s : st) {
        str.push_back(s);
        mp[s] = cnt;
        cnt += 1;
    }
    int sz = str.size();
    vector<vector<int>> adj(sz);
    for (auto it : edge) {
        int u = mp[it[0]], v = mp[it[1]];
        adj[u].push_back(v);
    }

    queue<array<int, 2>> q;
    for (int i = 0; i < sz; i++) {
        cnt = 0;

        for (int j = 0; j < 3; j++) {
            if (str[i][j] != arr[0][j]) cnt += 1;
        }
        q.push({cnt, i});
    }

    cnt = 0;
    int ans = INT_MAX;
    vector<int> dis(sz, INT_MAX);
    while (cnt < n) {
        cnt += 1;
        set<int> id;
        while (q.size()) {
            array<int, 2> tmp = q.front();
            q.pop();
            if (cnt == n) {
                ans = min(ans, tmp[0]);
                continue;
            }

            for (int a : adj[tmp[1]]) {
                int chk = 0;
                for (int i = 0; i < 3; i++) {
                    if (arr[cnt][i] != str[a][i]) {
                        chk += 1;
                    }
                }
                dis[a] = min(dis[a], tmp[0] + chk);
                id.insert(a);
            }
        }

        for (int x : id) {
            q.push({dis[x], x});
            dis[x] = INT_MAX;
        }
    }
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    private Map<String, Integer> portMap = new LinkedHashMap();
    private Map<String, List<String>> graph = new HashMap();
    private int index = 0;
    private int infi = Integer.MAX_VALUE / 2;
    private int ans = Integer.MAX_VALUE;
    private Set<String> ports = new HashSet();
    public int solve(String[] itinerary, String[][] edges) {
        for (String[] edge : edges) {
            String u = edge[0];
            String v = edge[1];
            // incoming edges
            graph.computeIfAbsent(v, k -> new ArrayList()).add(u);
            if (!portMap.containsKey(u)) {
                portMap.put(u, index++);
            }
            if (!portMap.containsKey(v)) {
                portMap.put(v, index++);
            }
            ports.add(u);
            ports.add(v);
        }
        List<String> portList = new ArrayList(ports);
        int[][] dp = new int[portList.size()][itinerary.length];

        for (int i = 0; i < portList.size(); i++) {
            String port = portList.get(i);
            dp[portMap.get(port)][0] = getDiff(port, itinerary[0]);
        }

        for (int idx = 1; idx < itinerary.length; idx++) {
            for (int j = 0; j < portList.size(); j++) {
                String port = portList.get(j);
                int diff = getDiff(port, itinerary[idx]);
                if (graph.get(port) == null) {
                    dp[portMap.get(port)][idx] = infi;
                } else {
                    int min = Integer.MAX_VALUE;
                    for (String prevPort : graph.get(port)) {
                        min = Math.min(min, dp[portMap.get(prevPort)][idx - 1] + diff);
                    }
                    dp[portMap.get(port)][idx] = min;
                }
            }
        }
        for (int i = 0; i < portList.size(); i++) {
            ans = Math.min(ans, dp[portMap.get(portList.get(i))][itinerary.length - 1]);
        }
        return ans;
    }

    private int getDiff(String str1, String str2) {
        int count = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i))
                ++count;
        }
        return count;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, itinerary, edges):
        n = len(itinerary)

        def diff(a, b):
            """The cost to change the airport name `a` to `b` is the number of different characters."""
            return sum(x != y for x, y in zip(a, b))

        # We will use dynamic programming.
        # dp[port] is the minimum cost to reach airport `port`.

        # We can freely change the first airport in the itinerary,
        # incurring only the cost of the name change itself.
        dp = dict()
        airports = set(e[0] for e in edges)
        for p in airports:
            dp[p] = diff(itinerary[0], p)

        for i in range(1, n):
            nextdp = dict()
            for p1, p2 in edges:
                # If it's possible to reach p1 at the previous index...
                if p1 in dp:
                    # then it's now possible to reach p2 at the current index.
                    # We incur an additional cost to change `itinerary[i]` to `p2`.
                    cost = dp[p1] + diff(itinerary[i], p2)
                    if p2 not in nextdp or cost < nextdp[p2]:
                        nextdp[p2] = cost
            dp = nextdp

        # Choose the lowest cost among all possible final airports.
        return min(dp.values())