Watch 5 video solutions for The Most Similar Path in a Graph, a hard level problem involving Dynamic Programming, Graph. This walkthrough by Abrar Sher has 5,164 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 <= 100m == roads.lengthn - 1 <= m <= (n * (n - 1) / 2)0 <= ai, bi <= n - 1ai != binames.length == nnames[i].length == 3names[i] consists of upper-case English letters.1 <= targetPath.length <= 100targetPath[i].length == 3targetPath[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?
Problem Overview: You are given an undirected graph of cities where each city has a name. The goal is to build a path of length m whose sequence of city names is as similar as possible to a given targetPath. Similarity is measured by the number of mismatched names, and the task is to return the path with the minimum mismatch cost.
Approach 1: Brute Force DFS Enumeration (Exponential Time)
One direct idea is to generate every possible path of length m in the graph using depth-first search. For each candidate path, compare the city names with targetPath and count mismatches. Track the path with the smallest cost. This approach explores all possible transitions between neighboring cities at each step, which leads to exponential growth in the number of paths. The time complexity is roughly O(n * degree^m) in the worst case, with O(m) space for recursion. It only works for very small graphs and mainly helps illustrate the search space.
Approach 2: Dynamic Programming on Graph Paths (O(m * E))
The efficient solution treats the problem as a dynamic programming transition across the graph. Let dp[i][v] represent the minimum mismatch cost to build a path of length i + 1 that ends at city v. For each step i, iterate over all cities and transition from their neighbors using the road connections. The cost adds 1 if the city name differs from targetPath[i], otherwise 0. This converts the problem into repeatedly relaxing transitions across edges, similar to shortest-path relaxation.
While filling the DP table, store a parent pointer to reconstruct the final path. After processing all m positions, choose the city with the minimum cost in the last layer and backtrack using the stored parents. Because each DP layer processes all edges, the total time complexity is O(m * E), where E is the number of roads. The space complexity is O(m * n) for the DP table and parent tracking.
This approach combines ideas from dynamic programming and graph traversal. Conceptually, it resembles computing a shortest path through layers of states, where each layer corresponds to a position in the target sequence. The mismatch penalty acts as the edge weight.
Recommended for interviews: The dynamic programming approach is what interviewers expect. Brute force demonstrates you understand the search space, but the layered DP transition across graph edges shows the ability to model the problem as a shortest-path style DP. Recognizing the state (position, city) and optimizing transitions is the key insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS Path Enumeration | O(n * degree^m) | O(m) | Only for conceptual understanding or extremely small graphs |
| Dynamic Programming on Graph Layers | O(m * E) | O(m * n) | General solution expected in interviews and coding platforms |