Minimum cost to convert string ii

impl Solution {
  pub fn minimum_cost(source: String, target: String, original: Vec<String>, changed: Vec<String>, cost: Vec<i32>) -> i64 {
    use std::collections::HashMap;
    let inf = i64::MAX / 2;
    let n = source.len();
    let sb = source.as_bytes();
    let tb = target.as_bytes();

    // Assign IDs to unique strings; remember string per ID
    let mut id_map: HashMap<String, usize> = HashMap::new();
    let mut id_to_str: Vec<String> = Vec::new();

    let get_id = |s: &str, id_map: &mut HashMap<String, usize>, id_to_str: &mut Vec<String>| -> usize {
      if let Some(&id) = id_map.get(s) {
        id
      } else {
        let id = id_to_str.len();
        id_map.insert(s.to_string(), id);
        id_to_str.push(s.to_string());
        id
      }
    };

    let k = original.len();
    let mut edges: Vec<(usize, usize, i64)> = Vec::with_capacity(k);
    for i in 0..k {
      let o = get_id(&original[i], &mut id_map, &mut id_to_str);
      let c = get_id(&changed[i], &mut id_map, &mut id_to_str);
      edges.push((o, c, cost[i] as i64));
    }

    let num_nodes = id_to_str.len();

    // Build distance matrix
    let mut dist = vec![vec![inf; num_nodes]; num_nodes];
    for i in 0..num_nodes { dist[i][i] = 0; }
    for &(o, c, w) in &edges {
      dist[o][c] = dist[o][c].min(w);
    }
    // Floyd-Warshall
    for mid in 0..num_nodes {
      for i in 0..num_nodes {
        if dist[i][mid] == inf { continue; }
        for j in 0..num_nodes {
          if dist[mid][j] < inf && dist[i][mid] + dist[mid][j] < dist[i][j] {
            dist[i][j] = dist[i][mid] + dist[mid][j];
          }
        }
      }
    }

    // Build map: (start_pos) -> list of (x_id, y_id, cost, len) via trie-like string matching
    // For efficiency: group pairs by length, then for each (i, len) match source[i..i+len] to x and target[i..i+len] to y
    // Strategy: for each pair (x_id, y_id) with dist < INF and same length, precompute positions where source matches x
    // Then at DP time, check both source and target match.

    // For each position i, collect all valid (x_id, y_id, cost) where
    // source[i..i+len] == str_x, target[i..i+len] == str_y, dist[x][y] < INF

    // Precompute: for each (x_id, y_id) pair with dist < INF and same length, check at each pos
    // Since num_nodes <= 200, pairs <= 40000; each pair has len <= 1000; positions <= 1000
    // Total work: 40000 * 1000 = 40M in worst case - acceptable

    // DP
    let mut dp = vec![inf; n + 1];
    dp[n] = 0;

    for i in (0..n).rev() {
      // Option: source[i] == target[i]: dp[i] = dp[i+1]
      if sb[i] == tb[i] && dp[i + 1] < inf {
        dp[i] = dp[i + 1];
      }

      // Option: convert source[i..i+len] using some transformation
      for x_id in 0..num_nodes {
        let x_str = &id_to_str[x_id];
        let len = x_str.len();
        if i + len > n { continue; }
        if &source[i..i + len] != x_str.as_str() { continue; }

        let t_sub = &target[i..i + len];
        if let Some(&y_id) = id_map.get(t_sub) {
          let d = dist[x_id][y_id];
          if d < inf && dp[i + len] < inf {
            dp[i] = dp[i].min(d + dp[i + len]);
          }
        }
      }
    }

    if dp[0] >= inf { -1 } else { dp[0] }
  }
}