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 3 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:

Follow-up: If each node can be visited only once in the path, What should you change in your solution?

Example 1:

Input: n = 5, roads = [[0,2],[0,3],[1,2],[1,3],[1,4],[2,4]], names = ["ATL","PEK","LAX","DXB","HND"], targetPath = ["ATL","DXB","HND","LAX"]
Output: [0,2,4,2]
Explanation: [0,2,4,2], [0,3,0,2] and [0,3,1,2] are accepted answers.
[0,2,4,2] is equivalent to ["ATL","LAX","HND","LAX"] which has edit distance = 1 with targetPath.
[0,3,0,2] is equivalent to ["ATL","DXB","ATL","LAX"] which has edit distance = 1 with targetPath.
[0,3,1,2] is equivalent to ["ATL","DXB","PEK","LAX"] which has edit distance = 1 with targetPath.

Example 2:

Input: n = 4, roads = [[1,0],[2,0],[3,0],[2,1],[3,1],[3,2]], names = ["ATL","PEK","LAX","DXB"], targetPath = ["ABC","DEF","GHI","JKL","MNO","PQR","STU","VWX"]
Output: [0,1,0,1,0,1,0,1]
Explanation: Any path in this graph has edit distance = 8 with targetPath.

Example 3:

Input: n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[4,5]], names = ["ATL","PEK","LAX","ATL","DXB","HND"], targetPath = ["ATL","DXB","HND","DXB","ATL","LAX","PEK"]
Output: [3,4,5,4,3,2,1]
Explanation: [3,4,5,4,3,2,1] is the only path with edit distance = 0 with targetPath.
It's equivalent to ["ATL","DXB","HND","DXB","ATL","LAX","PEK"]

Constraints:

• 2 <= n <= 100

• m == roads.length

• n - 1 <= m <= (n * (n - 1) / 2)

• 0 <= ai, bi <= n - 1

• ai != bi

• The graph is guaranteed to be connected and each pair of nodes may have at most one direct road.

• names.length == n

• names[i].length == 3

• names[i] consists of upper-case English letters.

• There can be two cities with the same name.

• 1 <= targetPath.length <= 100

• targetPath[i].length == 3

• targetPath[i] consists of upper-case English letters.

Solution

Intuition: I can only come up with a BFS solution. It will need to check all possible paths witch its length is equal to targetPath's length.

So the question is the same as the minimum edit count for a Node that appeared in the last step(in that case, its length is equal to the target's length).

We can define a table for it dist[i][j], where it denotes the minimum edit count for the Node i appear in step j. With the dynamic programing approach, we derive from the basic case (dp[i][0]) to the final anwser (dp[i][lastStep]), and find the minimum edit count among them.

• Build a Graph to make the iteration easier.

• Using Dijkstra to find the min edit of each path

  • PriorityQueue

    • dist[i][j] to keep the edit count for the case that node[i] appear in j-th step of target Path

      • Keep updating dist[i][j] and the PrevIndex in this case

    • Add next adjacent element into the queue with position increased by 1

  • Once the path length is the same as the targetPath length, then stop

    public List<Integer> mostSimilar(int n, int[][] roads, String[] names, String[] targetPath) {
        int m = targetPath.length;
        
        Map<Integer, List<Integer>> map = new HashMap<>();
        
        for(int[] road : roads) {
            if(!map.containsKey(road[0])) {
                map.put(road[0], new ArrayList<Integer>());
            }
            if(!map.containsKey(road[1])) {
                map.put(road[1], new ArrayList<Integer>());
            }
            map.get(road[0]).add(road[1]);
            map.get(road[1]).add(road[0]);
        }
        
        int[][] dist = new int[n][m];
        int[][] prevIndex = new int[n][m];
        int last = -1;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
            int da = dist[a[0]][a[1]];
            int db = dist[b[0]][b[1]];
            if (da == db) return b[1] - a[1];
            return da - db;
        });
        
        for(int i = 0; i < n; i++){
            for(int j = 1; j < m; j++){
                dist[i][j] = Integer.MAX_VALUE;
            }
            dist[i][0] = (names[i].equals(targetPath[0])) ? 0 : 1;
            pq.add(new int[]{i, 0});
        }
        
        while(!pq.isEmpty()){
            int[] node = pq.poll();
            int pos = node[1];
            int index = node[0];
            if(pos == m-1) {
                //System.out.println(dist[index][pos] );
                last = index;
                break;
            }
            for(int next : map.get(index)){
                 int newDist = dist[index][pos] + (names[next].equals(targetPath[pos+1]) ? 0 : 1);
                 if(newDist < dist[next][pos+1]){
                     dist[next][pos+1] = newDist;
                     prevIndex[next][pos+1] = index;
                     pq.add(new int[]{next, pos+1});
                 }
            }
        }
        LinkedList<Integer> ret = new LinkedList<>();
        for(int i = m-1; i >= 0; i--){
            ret.addFirst(last);
            last = prevIndex[last][i];
        }
        return ret;
    }