Minimum Cost to Convert String I

Leetcode Problem:

• Minimum Cost to Convert String I

Summary

• Given two strings source and target, and two character arrays original and changed, find the minimum cost to convert source to target using any number of operations.

Approach

• Dynamic programming is used to find the minimum cost
• The cost of changing each character in source to the corresponding character in target is calculated and stored in a 2D array minCost
• Then, the minimum cost of changing each character in source to any character in target is calculated using the Floyd-Warshall algorithm
• Finally, the minimum cost to convert source to target is calculated by summing up the minimum cost of changing each character in source to the corresponding character in target.

Complexity

• O(n^3), where n is the length of the strings source and target.

Explain

• The solution first initializes a 2D array minCost with all elements set to 1234567890
• Then, it calculates the minimum cost of changing each character in source to the corresponding character in target and stores it in minCost
• After that, it uses the Floyd-Warshall algorithm to calculate the minimum cost of changing each character in source to any character in target
• Finally, it calculates the minimum cost to convert source to target by summing up the minimum cost of changing each character in source to the corresponding character in target.

Solution Code:

class Solution {
public:
    long long minCost[26][26];
    long long minimumCost(string source, string target, vector& original, vector& changed, vector& cost) {
        for(int i = 0; i < 26; i++){
            for(int j = 0 ; j < 26; j++){
                minCost[i][j] = 1234567890;
            }
        }

        for(int i = 0 ; i < original.size(); i++){
            int a = original[i] -'a';
            int b = changed[i] - 'a';
            if (minCost[a][b] > cost[i]){
                minCost[a][b] = cost[i];
            }
        }

        for(int k = 0 ; k < 26; k++){
            for(int i = 0 ; i < 26; i++){
                if (k == i) continue;
                for(int j = 0 ; j < 26; j++){
                    if(k == j || i == j) continue;
                    if (minCost[i][j] <= minCost[i][k] + minCost[k][j]){
                        continue;
                    }
                    minCost[i][j] = minCost[i][k] + minCost[k][j];
                }
            }
        }
        long long ans = 0;
        for(int i = 0 ; i < source.size(); i++){
            int a = source[i] - 'a';
            int b = target[i] - 'a';
            if (a == b) continue;
            if(minCost[a][b] == 1234567890) return -1;
            ans += minCost[a][b];
        }
        return ans;
    }
};