Question

2976. Minimum Cost to Convert String I

中文文档

Description

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].

You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.

Return _the minimum cost to convert the string _source_ to the string _target_ using any number of operations. If it is impossible to convert_ source _to_ target, _return_ -1.

Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

 

Example 1:

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert the string "abcd" to string "acbe":
- Change value at index 1 from 'b' to 'c' at a cost of 5.
- Change value at index 2 from 'c' to 'e' at a cost of 1.
- Change value at index 2 from 'e' to 'b' at a cost of 2.
- Change value at index 3 from 'd' to 'e' at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28.
It can be shown that this is the minimum possible cost.

Example 2:

Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.

Example 3:

Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
Output: -1
Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.

 

Constraints:

• 1 <= source.length == target.length <= 105
• source, target consist of lowercase English letters.
• 1 <= cost.length == original.length == changed.length <= 2000
• original[i], changed[i] are lowercase English letters.
• 1 <= cost[i] <= 106
• original[i] != changed[i]

Solutions

Solution 1: Floyd Algorithm

According to the problem description, we can consider each letter as a node, and the conversion cost between each pair of letters as a directed edge. We first initialize a $26 \times 26$ two-dimensional array $g$, where $g[i][j]$ represents the minimum cost of converting letter $i$ to letter $j$. Initially, $g[i][j] = \infty$, and if $i = j$, then $g[i][j] = 0$.

Next, we traverse the arrays $original$, $changed$, and $cost$. For each index $i$, we update the cost $cost[i]$ of converting $original[i]$ to $changed[i]$ to $g[original[i]][changed[i]]$, taking the minimum value.

Then, we use the Floyd algorithm to calculate the minimum cost between any two nodes in $g$. Finally, we traverse the strings $source$ and $target$. If $source[i] \neq target[i]$ and $g[source[i]][target[i]] \geq \infty$, it means that the conversion cannot be completed, so we return $-1$. Otherwise, we add $g[source[i]][target[i]]$ to the answer.

After the traversal ends, we return the answer.

The time complexity is $O(m + n + |\Sigma|^3)$, and the space complexity is $O(|\Sigma|^2)$. Where $m$ and $n$ are the lengths of the arrays $original$ and $source$ respectively; and $|\Sigma|$ is the size of the alphabet, that is, $|\Sigma| = 26$.

class Solution:
  def minimumCost(
    self,
    source: str,
    target: str,
    original: List[str],
    changed: List[str],
    cost: List[int],
  ) -> int:
    g = [[inf] * 26 for _ in range(26)]
    for i in range(26):
      g[i][i] = 0
    for x, y, z in zip(original, changed, cost):
      x = ord(x) - ord('a')
      y = ord(y) - ord('a')
      g[x][y] = min(g[x][y], z)
    for k in range(26):
      for i in range(26):
        for j in range(26):
          g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    ans = 0
    for a, b in zip(source, target):
      if a != b:
        x, y = ord(a) - ord('a'), ord(b) - ord('a')
        if g[x][y] >= inf:
          return -1
        ans += g[x][y]
    return ans

class Solution {
  public long minimumCost(
    String source, String target, char[] original, char[] changed, int[] cost) {
    final int inf = 1 << 29;
    int[][] g = new int[26][26];
    for (int i = 0; i < 26; ++i) {
      Arrays.fill(g[i], inf);
      g[i][i] = 0;
    }
    for (int i = 0; i < original.length; ++i) {
      int x = original[i] - 'a';
      int y = changed[i] - 'a';
      int z = cost[i];
      g[x][y] = Math.min(g[x][y], z);
    }
    for (int k = 0; k < 26; ++k) {
      for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < 26; ++j) {
          g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }
    long ans = 0;
    int n = source.length();
    for (int i = 0; i < n; ++i) {
      int x = source.charAt(i) - 'a';
      int y = target.charAt(i) - 'a';
      if (x != y) {
        if (g[x][y] >= inf) {
          return -1;
        }
        ans += g[x][y];
      }
    }
    return ans;
  }
}

class Solution {
public:
  long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
    const int inf = 1 << 29;
    int g[26][26];
    for (int i = 0; i < 26; ++i) {
      fill(begin(g[i]), end(g[i]), inf);
      g[i][i] = 0;
    }

    for (int i = 0; i < original.size(); ++i) {
      int x = original[i] - 'a';
      int y = changed[i] - 'a';
      int z = cost[i];
      g[x][y] = min(g[x][y], z);
    }

    for (int k = 0; k < 26; ++k) {
      for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < 26; ++j) {
          g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }

    long long ans = 0;
    int n = source.length();
    for (int i = 0; i < n; ++i) {
      int x = source[i] - 'a';
      int y = target[i] - 'a';
      if (x != y) {
        if (g[x][y] >= inf) {
          return -1;
        }
        ans += g[x][y];
      }
    }
    return ans;
  }
};

func minimumCost(source string, target string, original []byte, changed []byte, cost []int) (ans int64) {
  const inf = 1 << 29
  g := make([][]int, 26)
  for i := range g {
    g[i] = make([]int, 26)
    for j := range g[i] {
      if i == j {
        g[i][j] = 0
      } else {
        g[i][j] = inf
      }
    }
  }

  for i := 0; i < len(original); i++ {
    x := int(original[i] - 'a')
    y := int(changed[i] - 'a')
    z := cost[i]
    g[x][y] = min(g[x][y], z)
  }

  for k := 0; k < 26; k++ {
    for i := 0; i < 26; i++ {
      for j := 0; j < 26; j++ {
        g[i][j] = min(g[i][j], g[i][k]+g[k][j])
      }
    }
  }
  n := len(source)
  for i := 0; i < n; i++ {
    x := int(source[i] - 'a')
    y := int(target[i] - 'a')
    if x != y {
      if g[x][y] >= inf {
        return -1
      }
      ans += int64(g[x][y])
    }
  }
  return
}

function minimumCost(
  source: string,
  target: string,
  original: string[],
  changed: string[],
  cost: number[],
): number {
  const g: number[][] = Array.from({ length: 26 }, () => Array(26).fill(Infinity));
  for (let i = 0; i < 26; ++i) {
    g[i][i] = 0;
  }
  for (let i = 0; i < original.length; ++i) {
    let x: number = original[i].charCodeAt(0) - 'a'.charCodeAt(0);
    let y: number = changed[i].charCodeAt(0) - 'a'.charCodeAt(0);
    let z: number = cost[i];
    g[x][y] = Math.min(g[x][y], z);
  }

  for (let k = 0; k < 26; ++k) {
    for (let i = 0; i < 26; ++i) {
      for (let j = 0; j < 26; ++j) {
        g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }

  let ans: number = 0;
  let n: number = source.length;
  for (let i = 0; i < n; ++i) {
    let x: number = source.charCodeAt(i) - 'a'.charCodeAt(0);
    let y: number = target.charCodeAt(i) - 'a'.charCodeAt(0);
    if (x !== y) {
      if (g[x][y] >= Infinity) {
        return -1;
      }
      ans += g[x][y];
    }
  }
  return ans;
}