The Most Similar Path in a Graph - Practice Coding Problems

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:

Edit distance is the number of positions where the path differs from the target path
Lower edit distance means the path is more similar to the target

Input & Output

Example 1 — Basic Graph Path

$ Input: n = 5, roads = [[0,1],[1,2],[2,3],[3,4],[1,4]], names = ["AAA","BBB","CCC","DDD","EEE"], targetPath = ["AAA","CCC"]

› Output: [0,2]

💡 Note: Path [0,2] gives ["AAA","CCC"] with edit distance 0 (perfect match). Other paths like [0,1] would give ["AAA","BBB"] with edit distance 1.

Example 2 — Minimum Edit Distance

$ Input: n = 4, roads = [[0,1],[1,2],[2,3],[0,3]], names = ["ATL","PEK","LAX","DXB"], targetPath = ["ABC","DEF","GHI"]

› Output: [0,1,2]

💡 Note: No perfect match exists. Path [0,1,2] gives ["ATL","PEK","LAX"] with edit distance 3 (all positions differ from ["ABC","DEF","GHI"]).

Example 3 — Single City Path

$ Input: n = 2, roads = [[0,1]], names = ["AAA","BBB"], targetPath = ["BBB"]

› Output: [1]

💡 Note: Target has length 1. City 1 has name "BBB" which exactly matches targetPath[0], giving edit distance 0.

Constraints

2 ≤ n ≤ 100
n - 1 ≤ roads.length ≤ n × (n - 1) / 2
roads[i].length == 2
0 ≤ ai, bi ≤ n - 1
ai ≠ bi
names.length == n
names[i].length == 3
names[i] consists of uppercase English letters
1 ≤ targetPath.length ≤ 100
targetPath[i].length == 3
targetPath[i] consists of uppercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Cities connected by roads with 3-letter names

Target Path

Sequence of city names we want to match

Find Best Path

Valid path with minimum edit distance to target

Key Takeaway

🎯 Key Insight: Use dynamic programming to efficiently explore all valid paths and track minimum edit distance at each step

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to use dynamic programming to track the minimum edit distance at each position and city. Build a DP table where dp[i][j] represents the minimum edit distance to reach city j at position i, then reconstruct the optimal path. Best approach is DP with backtracking. Time: O(k × n × m), Space: O(k × n)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming Solution	O(k × n × m)	O(k × n)	Use 2D DP to track minimum edit distance at each position and city
Brute Force - Try All Paths	O(n^k)	O(k)	Generate all possible paths of target length and find minimum edit distance

Dynamic Programming Solution — Algorithm Steps

Initialize DP table with infinity
Set dp[0][city] based on first target position
Fill DP table using transitions between connected cities
Backtrack to reconstruct optimal path

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

Set dp[0][city] based on first target

Fill Table

For each position, find minimum cost transitions

Reconstruct

Backtrack to build optimal path

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_CITIES 100
#define MAX_NAME_LEN 4

int graph[MAX_CITIES][MAX_CITIES];
int graphSize[MAX_CITIES];
int dp[MAX_CITIES][MAX_CITIES];
int parent[MAX_CITIES][MAX_CITIES];

int* solution(int n, int roads[][2], int roadsSize, char names[][MAX_NAME_LEN], char targetPath[][MAX_NAME_LEN], int targetPathSize, int* returnSize) {
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < roadsSize; i++) {
        int a = roads[i][0], b = roads[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
    }
    
    int k = targetPathSize;
    
    // Initialize DP table
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = INT_MAX;
            parent[i][j] = -1;
        }
    }
    
    // Initialize first position
    for (int city = 0; city < n; city++) {
        dp[0][city] = (strcmp(names[city], targetPath[0]) == 0) ? 0 : 1;
    }
    
    // Fill DP table
    for (int i = 1; i < k; i++) {
        for (int city = 0; city < n; city++) {
            int cost = (strcmp(names[city], targetPath[i]) == 0) ? 0 : 1;
            
            // Try coming from each neighbor
            for (int j = 0; j < graphSize[city]; j++) {
                int prevCity = graph[city][j];
                if (dp[i-1][prevCity] != INT_MAX && dp[i-1][prevCity] + cost < dp[i][city]) {
                    dp[i][city] = dp[i-1][prevCity] + cost;
                    parent[i][city] = prevCity;
                }
            }
        }
    }
    
    // Find best ending city
    int minDist = INT_MAX;
    int endCity = 0;
    for (int city = 0; city < n; city++) {
        if (dp[k-1][city] < minDist) {
            minDist = dp[k-1][city];
            endCity = city;
        }
    }
    
    // Reconstruct path
    int* path = (int*)malloc(k * sizeof(int));
    int city = endCity;
    for (int i = k-1; i >= 0; i--) {
        path[i] = city;
        if (i > 0) {
            city = parent[i][city];
        }
    }
    
    *returnSize = k;
    return path;
}

int main() {
    // Simplified parsing for demo
    int n = 5;
    int roads[][2] = {{0,1},{1,2},{2,3},{3,4},{1,4}};
    char names[][MAX_NAME_LEN] = {"AAA", "BBB", "CCC", "DDD", "EEE"};
    char targetPath[][MAX_NAME_LEN] = {"AAA", "CCC", "DDD"};
    
    int returnSize;
    int* result = solution(n, roads, 5, names, targetPath, 3, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n × m)

Where k is target path length, n is cities, m is edges - we fill k×n DP table and check m edges per position

✓ Linear Growth

Space Complexity

O(k × n)

DP table stores k×n states plus adjacency list O(m) and parent tracking O(k×n)

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

542 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler