Skip to content

2976. Minimum Cost to Convert String I 👍

  • Time: $O(|\texttt{original}| + 26^3 + |\texttt{source}|)$
  • Space: $O(26^2 + |\texttt{source}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  long long minimumCost(string source, string target, vector<char>& original,
                        vector<char>& changed, vector<int>& cost) {
    long ans = 0;
    // dist[u][v] := the minimum distance to change ('a' + u) to ('a' + v)
    vector<vector<long>> dist(26, vector<long>(26, LONG_MAX));

    for (int i = 0; i < cost.size(); ++i) {
      const int u = original[i] - 'a';
      const int v = changed[i] - 'a';
      dist[u][v] = min(dist[u][v], static_cast<long>(cost[i]));
    }

    for (int k = 0; k < 26; ++k)
      for (int i = 0; i < 26; ++i)
        if (dist[i][k] < LONG_MAX)
          for (int j = 0; j < 26; ++j)
            if (dist[k][j] < LONG_MAX)
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    for (int i = 0; i < source.length(); ++i) {
      if (source[i] == target[i])
        continue;
      const int u = source[i] - 'a';
      const int v = target[i] - 'a';
      if (dist[u][v] == LONG_MAX)
        return -1;
      ans += dist[u][v];
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public long minimumCost(String source, String target, char[] original, char[] changed,
                          int[] cost) {
    long ans = 0;
    // dist[u][v] := the minimum distance to change ('a' + u) to ('a' + v)
    long[][] dist = new long[26][26];
    Arrays.stream(dist).forEach(A -> Arrays.fill(A, Long.MAX_VALUE));

    for (int i = 0; i < cost.length; ++i) {
      final int u = original[i] - 'a';
      final int v = changed[i] - 'a';
      dist[u][v] = Math.min(dist[u][v], cost[i]);
    }

    for (int k = 0; k < 26; ++k)
      for (int i = 0; i < 26; ++i)
        if (dist[i][k] < Long.MAX_VALUE)
          for (int j = 0; j < 26; ++j)
            if (dist[k][j] < Long.MAX_VALUE)
              dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

    for (int i = 0; i < source.length(); ++i) {
      if (source.charAt(i) == target.charAt(i))
        continue;
      final int u = source.charAt(i) - 'a';
      final int v = target.charAt(i) - 'a';
      if (dist[u][v] == Long.MAX_VALUE)
        return -1;
      ans += dist[u][v];
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
  def minimumCost(
      self,
      source: str,
      target: str,
      original: list[str],
      changed: list[str],
      cost: list[int],
  ) -> int:
    ans = 0
    # dist[u][v] := the minimum distance to change ('a' + u) to ('a' + v)
    dist = [[math.inf] * 26 for _ in range(26)]

    for a, b, c in zip(original, changed, cost):
      u = ord(a) - ord('a')
      v = ord(b) - ord('a')
      dist[u][v] = min(dist[u][v], c)

    for k in range(26):
      for i in range(26):
        if dist[i][k] < math.inf:
          for j in range(26):
            if dist[k][j] < math.inf:
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    for s, t in zip(source, target):
      if s == t:
        continue
      u = ord(s) - ord('a')
      v = ord(t) - ord('a')
      if dist[u][v] == math.inf:
        return -1
      ans += dist[u][v]

    return ans