Skip to main content
Talentd

The Most Similar Path in a Graph - Solution & Explanation

HardPremiumFree on FleetCodeDynamic ProgrammingGraph11 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 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?

Approach Overview

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.

Solution

We first build an adjacency list g based on the given roads, where g[i] represents the list of cities directly connected to city i.

Then we define f[i][j] to be the minimum edit distance of the first i cities of targetPath and the first j cities of names when city i of targetPath matches city j of names.

Then we can get the following recurrence equation:

$ f[i][j] = min_{k \in g[j]} f[i - 1][k] + (targetPath[i] neq names[j])

In the process of state transition, we record the predecessor city of each state, and finally restore the optimal path from the end to the beginning according to the predecessor city array pre.

The time complexity is O(m times n^2), and the space complexity is O(m times n). Where m and n are the lengths of targetPath and names$ respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force DFS Path EnumerationO(n * degree^m)O(m)Only for conceptual understanding or extremely small graphs
Dynamic Programming on Graph LayersO(m * E)O(m * n)General solution expected in interviews and coding platforms

Video Solution

LeetCode 1548. The Most Similar Path in a Graph • Abrar Sher • 5,166 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is The Most Similar Path in a Graph easy or hard?
The Most Similar Path in a Graph is classified as Hard because it combines graph traversal with dynamic programming. The difficulty comes from recognizing the correct state representation and implementing path reconstruction while keeping the transitions efficient.
The Most Similar Path in a Graph Python/Java solution
Most implementations follow the same DP pattern across languages. Build the adjacency list, initialize dp[0][v] based on the first target name, and update dp[i][v] by iterating over neighbors. The final path is reconstructed using stored parent pointers. This approach works consistently in Python, Java, C++, Go, and TypeScript.
How to solve The Most Similar Path in a Graph in O(m * E)?
Model the problem as layered dynamic programming. For each step i and city v, compute dp[i][v] as the minimum cost of reaching v from any neighbor at step i-1 plus the mismatch penalty with targetPath[i]. Iterate this transition for all m steps and store parent pointers to reconstruct the final path.
What is the best approach for The Most Similar Path in a Graph?
Dynamic programming on graph states is the best approach. Define dp[i][v] as the minimum mismatch cost when the path position is i and the current city is v. Transition from all neighboring cities and add a penalty if the city name differs from targetPath[i]. This runs in O(m * E) time and guarantees the optimal path.
Is The Most Similar Path in a Graph asked at Google/Amazon/Meta?
Graph dynamic programming and shortest-path style problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. The key skill tested is modeling a sequence alignment problem on a graph using DP states and transitions.
What data structure is used in The Most Similar Path in a Graph?
The main structures are an adjacency list to represent the graph and a 2D DP table dp[m][n] to track the minimum mismatch cost. A separate parent array is used to reconstruct the optimal path after computing the DP transitions.
What is the time complexity of The Most Similar Path in a Graph?
The optimal dynamic programming solution runs in O(m * E) time, where m is the length of targetPath and E is the number of edges in the graph. Each DP layer processes transitions across all edges. Space complexity is O(m * n) for storing DP values and parent pointers for path reconstruction.

Ready to solve this problem?

Practice The Most Similar Path in a Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching