Minimum cost to convert string i

Array String Graph Theory Shortest Path

63.2% acceptance

Feb 25, 2026

1332

You are given two strings source and target, char arrays original and changed, and int array cost. cost[i] = cost to change original[i] to changed[i]. Find minimum cost to convert source to target. Return -1 if impossible.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_cost(source: String, target: String, original: Vec<char>, changed: Vec<char>, cost: Vec<i32>) -> i64 {
    let inf = i64::MAX / 2;
    let mut dist = vec![vec![inf; 26]; 26];
    for i in 0..26 {
      dist[i][i] = 0;
    }
    for k in 0..original.len() {
      let o = (original[k] as u8 - b'a') as usize;
      let c = (changed[k] as u8 - b'a') as usize;
      dist[o][c] = dist[o][c].min(cost[k] as i64);
    }
    // Floyd-Warshall
    for mid in 0..26 {
      for i in 0..26 {
        for j in 0..26 {
          if dist[i][mid] < inf && dist[mid][j] < inf {
            dist[i][j] = dist[i][j].min(dist[i][mid] + dist[mid][j]);
          }
        }
      }
    }
    let sb = source.as_bytes();
    let tb = target.as_bytes();
    let mut total = 0i64;
    for i in 0..sb.len() {
      let s = (sb[i] - b'a') as usize;
      let t = (tb[i] - b'a') as usize;
      if s == t { continue; }
      if dist[s][t] >= inf { return -1; }
      total += dist[s][t];
    }
    total
  }
}