Problem statement

https://leetcode.com/problems/the-most-similar-path-in-a-graph/

Solution

Let dp(ind, node) be minimum distance if we now at index ind from T and in node node in our graph. Then to evaluate dp(ind, node) we need to check all neibours. Also we need to keep connections to previous optimal node, so in the end we can reconstruct solution. Also I add dummy node to graph, so we always finish at the node n.

Complexity

Time complexity is O(m*n^2), where m is length of T, space complexity is O(mn).

Code

class Solution:
    def mostSimilar(self, n, roads, names, T):
        G, end, ans = defaultdict(list), n, []
        for x, y in roads:
            G[x].append(y)
            G[y].append(x)
        
        for x in range(n):
            G[n].append(x)  #not add opposite edges though

        T, names = T + ["@@@"], names + ["@@@"]

        @lru_cache(None)
        def dp(ind, node):
            if ind == -1: return (0, -1)
            return min((dp(ind - 1, neib)[0] + int(names[node] != T[ind]), neib) for neib in G[node]) 

        for ind in range(len(T) - 1, -1, -1):
            ans.append(end)
            _, end = dp(ind, end)

        return ans[::-1][:-1]