minimumCost.txt

2976. Minimum Cost to Convert String I
Medium
Topics
Companies
Hint
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].

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char> changed, vector<int>& cost) {
        const long long inf = 1e18;
        vector<vector<long long>> c(26,vector<long long>(26,inf));
        int m = original.size();
        
        
        for(int i = 0; i < 26; i++)
            c[i][i] = 0;
        for(int i = 0; i < m; i++){
            c[original[i] - 'a'][changed[i] - 'a'] = min(c[original[i] - 'a'][changed[i] - 'a'], 1LL * cost[i]);
        }

        for(int k = 0; k < 26; k++){
            for(int i = 0; i < 26; i++){
                for(int j = 0; j < 26; j++){
                    c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
                }
            }
        }
        
        long long ans = 0;
        int n = source.length();
        for(int i = 0; i < n; i++){
            ans += c[source[i] - 'a'][target[i] - 'a'];
            if(ans >= inf) return -1;
        }
        
        return ans;
    }
};