The most similar path in a graph

Dynamic Programming Graph Theory

59.4% acceptance

Mar 31, 2026

380

187

No description available.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  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 t = target_path.len();
    let mut adj = vec![vec![]; n];
    for r in &roads {
      adj[r[0] as usize].push(r[1] as usize);
      adj[r[1] as usize].push(r[0] as usize);
    }
    // dp[i][v] = min edit distance for target_path[0..=i] ending at city v
    let mut dp = vec![vec![i32::MAX; n]; t];
    let mut parent = vec![vec![usize::MAX; n]; t];
    for v in 0..n {
      dp[0][v] = if names[v] != target_path[0] { 1 } else { 0 };
    }
    for i in 1..t {
      for v in 0..n {
        let cost = if names[v] != target_path[i] { 1 } else { 0 };
        for &u in &adj[v] {
          if dp[i - 1][u] + cost < dp[i][v] {
            dp[i][v] = dp[i - 1][u] + cost;
            parent[i][v] = u;
          }
        }
      }
    }
    // Find best ending city
    let mut best = 0;
    for v in 1..n {
      if dp[t - 1][v] < dp[t - 1][best] {
        best = v;
      }
    }
    // Backtrack
    let mut path = vec![0i32; t];
    path[t - 1] = best as i32;
    for i in (1..t).rev() {
      best = parent[i][best];
      path[i - 1] = best as i32;
    }
    path
  }
}