1548. The Most Similar Path in a Graph

We have n cities and m bi-directional roads where roads[i] = [ai, bi] connects city ai with city bi. Each city has a name consisting of exactly three upper-case English letters given in the string array names. Starting at any city x, you can reach any city y where y != x (i.e., the cities and the roads are forming an undirected connected graph).

You will be given a string array targetPath. You should find a path in the graph of the same length and with the minimum edit distance to targetPath.

You need to return the order of the nodes in the path with the minimum edit distance. The path should be of the same length of targetPath and should be valid (i.e., there should be a direct road between ans[i] and ans[i + 1]). If there are multiple answers return any one of them.

The edit distance is defined as follows:

class Solution {
    int dp[101][101];
    vector<string> na;
    vector<string> ta;
    vector<vector<int>> graph;
    vector<int> res;
    
    int solution(int r, int i) {
        if(ta.size() == i) return 0;
        if(dp[r][i] != -1) return dp[r][i];
        int cost = INT_MAX;
        for(auto near : graph[r]) {
            auto nc = solution(near,i+1);
            if(nc < cost) {
                cost = nc;
            }
        }
        return dp[r][i] = cost + (ta[i] != na[r]);
    }
    
    void reverse(int p, int i) {
        if(ta.size() == i) return;
        int mi = INT_MAX, n;
        res.push_back(p);
        for(auto near : graph[p]) {
            auto nc = solution(near, i + 1);
            if(nc < mi) {
                mi = nc; n = near;
            }
        }
        reverse(n,i+1);
    }
public:
    vector<int> mostSimilar(int n, vector<vector<int>>& roads, vector<string>& names, vector<string>& targetPath) {
        na = names, ta = targetPath;
        graph = vector<vector<int>>(n,vector<int>());
        for(auto road : roads) {
            graph[road[0]].push_back(road[1]);
            graph[road[1]].push_back(road[0]);
        }
        memset(dp,-1,sizeof(dp));
        int mi = INT_MAX, st;
        for(int i = 0; i < n; i++) {
            auto cost = solution(i, 0);
            if(cost < mi) {
                mi = cost;
                st = i;
            }
        }
        
        reverse(st,0);
        
        return res;

    }
};