The Most Similar Path in a Graph

Problem

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:

Examples

Example 1:

1
2
3
4
5
6
7


![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1500-1599/1548.The%20Most%20Similar%20Path%20in%20a%20Graph/images/e1.jpg)
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:

1
2
3
4


![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1500-1599/1548.The%20Most%20Similar%20Path%20in%20a%20Graph/images/e2.jpg)
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:

1
2
3
4
5


**![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1500-1599/1548.The%20Most%20Similar%20Path%20in%20a%20Graph/images/e3.jpg)**
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.

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

Solution

Approach

This problem is a classic example of using Dynamic Programming on Graphs. The goal is to find a path of the same length as targetPath with the minimum edit distance, where the edit distance is the number of positions where the city name in the path differs from the target.

We can use DP where dp[i][city] is the minimum edit distance to reach city at position i in the path. For each position, we try all possible cities and for each, try all possible previous cities that are connected to it. We also keep a parent table to reconstruct the path.

Steps:

Build the adjacency list for the graph.
Initialize dp and parent tables.
For each position in targetPath, for each city, update the minimum edit distance from all possible previous cities.
Find the city at the last position with the minimum edit distance and reconstruct the path using the parent table.

Code

1
2
3
4



We use dynamic programming to find the path of minimum edit distance. For each position in the target path and each city, we keep the minimum edit distance to reach that city at that position, and a parent pointer to reconstruct the path. The code below uses the backward DP approach, which is more efficient for this problem.

##### C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<int> mostSimilar(int n, vector<vector<int>>& roads, vector<string>& names, vector<string>& targetPath) {
    vector<vector<int>> graph(n);
    for (auto& r : roads) {
        graph[r[0]].push_back(r[1]);
        graph[r[1]].push_back(r[0]);
    }
    int m = targetPath.size();
    vector<vector<int>> dp(m, vector<int>(n, 1e9));
    vector<vector<int>> parent(m, vector<int>(n, -1));
    for (int i = 0; i < n; ++i)
        dp[m-1][i] = (names[i] == targetPath[m-1] ? 0 : 1);
    for (int i = m-2; i >= 0; --i) {
        for (int u = 0; u < n; ++u) {
            for (int v : graph[u]) {
                int cost = (names[u] == targetPath[i] ? 0 : 1) + dp[i+1][v];
                if (cost < dp[i][u]) {
                    dp[i][u] = cost;
                    parent[i][u] = v;
                }
            }
        }
    }
    int min_cost = 1e9, start = 0;
    for (int i = 0; i < n; ++i) {
        if (dp[0][i] < min_cost) {
            min_cost = dp[0][i];
            start = i;
        }
    }
    vector<int> path;
    int u = start;
    for (int i = 0; i < m; ++i) {
        path.push_back(u);
        u = parent[i][u];
    }
    return path;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


import java.util.*;
class Solution {
    public List<Integer> mostSimilar(int n, int[][] roads, List<String> names, List<String> targetPath) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; ++i) graph.add(new ArrayList<>());
        for (int[] r : roads) {
            graph.get(r[0]).add(r[1]);
            graph.get(r[1]).add(r[0]);
        }
        int m = targetPath.size();
        int[][] dp = new int[m][n];
        int[][] parent = new int[m][n];
        for (int[] row : dp) Arrays.fill(row, 1000000000);
        for (int[] row : parent) Arrays.fill(row, -1);
        for (int i = 0; i < n; ++i)
            dp[m-1][i] = names.get(i).equals(targetPath.get(m-1)) ? 0 : 1;
        for (int i = m-2; i >= 0; --i) {
            for (int u = 0; u < n; ++u) {
                for (int v : graph.get(u)) {
                    int cost = (names.get(u).equals(targetPath.get(i)) ? 0 : 1) + dp[i+1][v];
                    if (cost < dp[i][u]) {
                        dp[i][u] = cost;
                        parent[i][u] = v;
                    }
                }
            }
        }
        int minCost = 1000000000, start = 0;
        for (int i = 0; i < n; ++i) {
            if (dp[0][i] < minCost) {
                minCost = dp[0][i];
                start = i;
            }
        }
        List<Integer> path = new ArrayList<>();
        int u = start;
        for (int i = 0; i < m; ++i) {
            path.add(u);
            u = parent[i][u];
        }
        return path;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


from typing import List
def mostSimilar(n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:
    from collections import defaultdict
    graph = defaultdict(list)
    for a, b in roads:
        graph[a].append(b)
        graph[b].append(a)
    m = len(targetPath)
    dp = [[float('inf')] * n for _ in range(m)]
    parent = [[-1] * n for _ in range(m)]
    for i in range(n):
        dp[m-1][i] = 0 if names[i] == targetPath[m-1] else 1
    for i in range(m-2, -1, -1):
        for u in range(n):
            for v in graph[u]:
                cost = (0 if names[u] == targetPath[i] else 1) + dp[i+1][v]
                if cost < dp[i][u]:
                    dp[i][u] = cost
                    parent[i][u] = v
    min_cost, start = min((dp[0][i], i) for i in range(n))
    path = []
    u = start
    for i in range(m):
        path.append(u)
        u = parent[i][u]
    return path

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


use std::collections::HashMap;
pub fn most_similar(n: i32, roads: Vec<Vec<i32>>, names: Vec<String>, target_path: Vec<String>) -> Vec<i32> {
    let n = n as usize;
    let m = target_path.len();
    let mut graph = vec![vec![]; n];
    for r in &roads {
        graph[r[0] as usize].push(r[1] as usize);
        graph[r[1] as usize].push(r[0] as usize);
    }
    let mut dp = vec![vec![std::i32::MAX; n]; m];
    let mut parent = vec![vec![-1; n]; m];
    for i in 0..n {
        dp[m-1][i] = if names[i] == target_path[m-1] { 0 } else { 1 };
    }
    for i in (0..m-1).rev() {
        for u in 0..n {
            for &v in &graph[u] {
                let cost = (if names[u] == target_path[i] { 0 } else { 1 }) + dp[i+1][v];
                if cost < dp[i][u] {
                    dp[i][u] = cost;
                    parent[i][u] = v as i32;
                }
            }
        }
    }
    let (mut min_cost, mut start) = (std::i32::MAX, 0);
    for i in 0..n {
        if dp[0][i] < min_cost {
            min_cost = dp[0][i];
            start = i;
        }
    }
    let mut path = vec![];
    let mut u = start;
    for i in 0..m {
        path.push(u as i32);
        u = parent[i][u] as usize;
    }
    path
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


function mostSimilar(n: number, roads: number[][], names: string[], targetPath: string[]): number[] {
    const graph: number[][] = Array.from({length: n}, () => []);
    for (const [a, b] of roads) {
        graph[a].push(b);
        graph[b].push(a);
    }
    const m = targetPath.length;
    const dp: number[][] = Array.from({length: m}, () => Array(n).fill(Infinity));
    const parent: number[][] = Array.from({length: m}, () => Array(n).fill(-1));
    for (let i = 0; i < n; ++i) {
        dp[m-1][i] = names[i] === targetPath[m-1] ? 0 : 1;
    }
    for (let i = m-2; i >= 0; --i) {
        for (let u = 0; u < n; ++u) {
            for (const v of graph[u]) {
                const cost = (names[u] === targetPath[i] ? 0 : 1) + dp[i+1][v];
                if (cost < dp[i][u]) {
                    dp[i][u] = cost;
                    parent[i][u] = v;
                }
            }
        }
    }
    let minCost = Infinity, start = 0;
    for (let i = 0; i < n; ++i) {
        if (dp[0][i] < minCost) {
            minCost = dp[0][i];
            start = i;
        }
    }
    const path: number[] = [];
    let u = start;
    for (let i = 0; i < m; ++i) {
        path.push(u);
        u = parent[i][u];
    }
    return path;
}

Complexity Analysis

⏰ Time complexity: O(m * n * d) where m is the length of targetPath, n is the number of cities, and d is the average degree (max n).
🧺 Space complexity: O(m * n) for the DP and parent tables.

Problem#

Examples#

Solution#

Approach#

Steps:#

Code#

Complexity Analysis#