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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
// 2976. Minimum Cost to Convert String I
#include "leetcode.h"
/*
* 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 te 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, changed[j] == y'. return the minimum cost to conver the
* string 'source' to the string 'target'.
*/
class Solution {
public:
long long minimumCost(string source, string target, vector<char> &original,
vector<char> &changed, vector<int> &cost) {
long long ans = 0;
vector<vector<long long>> n(26, vector<long long>(26, INT_MAX));
for (int i = 0; i < original.size(); ++i) {
int s = original[i] = 'a', t = changed[i] - 'a';
n[s][t] = min(n[s][t], (long long)cost[i]);
}
for (int k = 0; k < 26; ++k)
for (int i = 0; i < 26; i++)
for (int j = 0; j < 26; j++)
n[i][j] = min(n[i][j], n[i][k] + n[k][j]);
for (int i = 0; i < source.size(); ++i) {
if (source[i] == target[i])
continue;
int s = source[i] - 'a', t = target[i] - 'a';
if (n[s][t] >= INT_MAX)
return -1;
ans += n[s][t];
}
return ans;
}
};
int main() {
Solution obj;
vector<char> o1 = {'a', 'b', 'c', 'c', 'e', 'd'},
ch1 = {'b', 'c', 'b', 'e', 'b', 'e'}, o2 = {'a', 'b'},
ch2 = {'c', 'b'}, o3 = {'a'}, ch3 = {'e'};
vector<int> co1 = {2, 5, 5, 1, 2, 20}, co2 = {1, 2}, co3 = {10000};
printf("%lld\n", obj.minimumCost("abcd", "acbe", o1, ch1, co1)); // expect: 28
printf("%lld\n", obj.minimumCost("aaaa", "bbbb", o2, ch2, co2)); // expect: 12
printf("%lld\n", obj.minimumCost("abcd", "acbe", o3, ch3, co3)); // expect: -1
}
|