Problem statement

https://binarysearch.com/problems/Fix-Flight-Itinerary/

Solution

Similar to Leetcode 1548 The Most Similar Path in a Graph.

Complexity

It is O(mn) for time, where n is the length of itinerary, m is the length of edges. Space is O(n * k), where k is number of cities.

Code

class Solution:
    def solve(self, T, edges):
        G, names = defaultdict(list), set()
        for x, y in edges:
            G[y] += [x]
            names.add(y)

        def diff(x, y):
            return sum(a != b for a, b in zip(x, y))
        
        @lru_cache(None)
        def dp(ind, node):
            if ind == -1: return 0
            if not G[node]:
                return diff(node, T[ind]) if ind == 0 else float("inf")
            return min([dp(ind - 1, neib) + diff(node, T[ind]) for neib in G[node]]) 

        return min(dp(len(T) - 1, x) for x in names)