You are given an undirected connected graph with n nodes, labeled from 0 to n - 1. The graph is represented by an edge list roads, where each edge connects two nodes.
You are also given a list of city names names, where names[i] is the name of node i, and a target path targetPath (a list of city names).
Your task is to find a path in the graph of the same length as targetPath (using nodes, possibly with repeats), such that the edit distance (the number of positions where the node's city name is different from the corresponding name in targetPath) is minimized.
Return the sequence of node indices of the most similar path. There is always at least one valid solution.
Constraints:
targetPath.
At a glance, this problem is about matching a sequence of city names to a path in a graph, minimizing the number of mismatches.
A brute-force solution would be to try every possible path of the required length and count mismatches, but the number of possible paths grows exponentially with the path length, making brute-force impractical for larger graphs or longer paths.
We need to optimize. Since the mismatch cost at each step depends only on the current node and the current position in targetPath, and the next step depends only on the current node, this suggests a dynamic programming (DP) approach. We can use memoization to avoid recomputing results for the same subproblems.
The problem is reminiscent of finding the shortest path, but instead of edge weights, our "cost" is the mismatch at each step. We want to build the path step by step, always keeping track of the minimal mismatch cost for each possible current node at each position in the targetPath.
The optimized solution uses dynamic programming (DP) with memoization. Here is the step-by-step breakdown:
roads input for fast neighbor lookup.dp[pos][city] be the minimal mismatch cost to reach position pos in targetPath when at node city.pos in targetPath and each node city, consider moving to any neighbor next_city in the next step.0 if names[city] == targetPath[pos], otherwise 1.dp[pos+1][next_city] if moving from city to next_city yields a lower cost.pos = 0, for every node city, set dp[0][city] to 0 if names[city] == targetPath[0], else 1.parent table that records from which node each step was reached.Example Input:
n = 5roads = [[0,2],[0,3],[1,2],[1,3],[1,4],[2,4]]names = ["ATL","PEK","LAX","DXB","HND"]targetPath = ["ATL","DXB","HND","LAX"]dp[0][0]=0, others get 1.dp[1][3]=0 (reached from 0 with cost 0+0=0).Brute-force Approach:
n^L), where n is the number of nodes and L is the length of targetPath (all possible paths).L) for the recursion stack or path storage.L * n^2), where for each of L positions, we consider all n nodes and their neighbors (up to n per node in the worst case).L * n) for the DP and parent tables.This problem is about finding a path in a graph that best matches a sequence of city names, minimizing mismatches. Brute-force is too slow, so we use dynamic programming to efficiently compute the minimal mismatch path. By defining the right DP state and using parent pointers for reconstruction, we solve the problem in polynomial time and space. The approach demonstrates the power of DP for pathfinding problems with custom cost functions.
from collections import defaultdict
class Solution:
def mostSimilar(self, n, roads, names, targetPath):
graph = [[] for _ in range(n)]
for u, v in roads:
graph[u].append(v)
graph[v].append(u)
L = len(targetPath)
dp = [[float('inf')] * n for _ in range(L)]
parent = [[-1] * n for _ in range(L)]
for city in range(n):
dp[0][city] = int(names[city] != targetPath[0])
for i in range(1, L):
for city in range(n):
for nei in graph[city]:
cost = dp[i-1][nei] + int(names[city] != targetPath[i])
if cost < dp[i][city]:
dp[i][city] = cost
parent[i][city] = nei
# Find end city with minimal cost
min_cost = float('inf')
last_city = -1
for city in range(n):
if dp[L-1][city] < min_cost:
min_cost = dp[L-1][city]
last_city = city
# Reconstruct path
path = [0] * L
path[-1] = last_city
for i in range(L-1, 0, -1):
path[i-1] = parent[i][path[i]]
return path
#include <vector>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
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 L = targetPath.size();
vector<vector<int>> dp(L, vector<int>(n, INT_MAX));
vector<vector<int>> parent(L, vector<int>(n, -1));
for (int city = 0; city < n; ++city) {
dp[0][city] = (names[city] != targetPath[0]);
}
for (int i = 1; i < L; ++i) {
for (int city = 0; city < n; ++city) {
for (int nei : graph[city]) {
int cost = dp[i-1][nei] + (names[city] != targetPath[i]);
if (cost < dp[i][city]) {
dp[i][city] = cost;
parent[i][city] = nei;
}
}
}
}
int min_cost = INT_MAX, last_city = -1;
for (int city = 0; city < n; ++city) {
if (dp[L-1][city] < min_cost) {
min_cost = dp[L-1][city];
last_city = city;
}
}
vector<int> path(L);
path[L-1] = last_city;
for (int i = L-1; i > 0; --i) {
path[i-1] = parent[i][path[i]];
}
return path;
}
};
import java.util.*;
class Solution {
public int[] mostSimilar(int n, int[][] roads, String[] names, 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 L = targetPath.length;
int[][] dp = new int[L][n];
int[][] parent = new int[L][n];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
for (int[] row : parent) Arrays.fill(row, -1);
for (int city = 0; city < n; ++city) {
dp[0][city] = names[city].equals(targetPath[0]) ? 0 : 1;
}
for (int i = 1; i < L; ++i) {
for (int city = 0; city < n; ++city) {
for (int nei : graph.get(city)) {
int cost = dp[i-1][nei] + (names[city].equals(targetPath[i]) ? 0 : 1);
if (cost < dp[i][city]) {
dp[i][city] = cost;
parent[i][city] = nei;
}
}
}
}
int minCost = Integer.MAX_VALUE, lastCity = -1;
for (int city = 0; city < n; ++city) {
if (dp[L-1][city] < minCost) {
minCost = dp[L-1][city];
lastCity = city;
}
}
int[] path = new int[L];
path[L-1] = lastCity;
for (int i = L-1; i > 0; --i) {
path[i-1] = parent[i][path[i]];
}
return path;
}
}
var mostSimilar = function(n, roads, names, targetPath) {
const graph = Array.from({length: n}, () => []);
for (const [u, v] of roads) {
graph[u].push(v);
graph[v].push(u);
}
const L = targetPath.length;
const dp = Array.from({length: L}, () => Array(n).fill(Infinity));
const parent = Array.from({length: L}, () => Array(n).fill(-1));
for (let city = 0; city < n; ++city) {
dp[0][city] = names[city] === targetPath[0] ? 0 : 1;
}
for (let i = 1; i < L; ++i) {
for (let city = 0; city < n; ++city) {
for (const nei of graph[city]) {
const cost = dp[i-1][nei] + (names[city] === targetPath[i] ? 0 : 1);
if (cost < dp[i][city]) {
dp[i][city] = cost;
parent[i][city] = nei;
}
}
}
}
let minCost = Infinity, lastCity = -1;
for (let city = 0; city < n; ++city) {
if (dp[L-1][city] < minCost) {
minCost = dp[L-1][city];
lastCity = city;
}
}
const path = Array(L);
path[L-1] = lastCity;
for (let i = L-1; i > 0; --i) {
path[i-1] = parent[i][path[i]];
}
return path;
};