2976. Minimum Cost to Convert String I.md

2976. Minimum Cost to Convert String I

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 <= 10^5
• source, target consists of lowercase English letters.
• 1 <= cost.length == original.length == changed.length <= 2000
• original[i], changed[i] are lowercase English letters.
• 1 <= cost[i] <= 10^6
• original[i] != changed[i]

---

Solution

Brief explanation of the problem and the solution.

Approach

Detailed explanation of the solution.

Explanation with example

explain the approach with an example.

Complexity

Let n be the length of the source and m be the length of the original array.

• Time Complexity:

  • Populating distances with the initial conversion costs takes O(m) time.

  • Each of the three nested loops runs 26 times. Thus, the overall time taken is O(26*3) = O(1).

  • To calculate the minTotalCost, the algorithm loops over the source string, which takes O(n) time.

  Thus, the time complexity of the algorithm is O(m)+O(1)+O(n), which simplifies to O(m+n).

• Space Complexity:

  • The distances array has a fixed size of 26×26. We do not use any other data structures dependent on the length of the input space. Thus, the algorithm has a constant O(1) space complexity.

Code

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        const int INF = 1e8 + 7;
        int n = 26;
        vector<vector<int>> distances(26, vector<int>(n, INF));

        for(int i=0; i<n; i++) {
            distances[i][i] = 0;
        }

        for(int i=0; i<original.size(); i++) {
            int u = original[i] - 'a';
            int v = changed[i] - 'a';
            int weight = cost[i];

            distances[u][v] = min(distances[u][v], weight); //directed graph
        }

        Floyd_Warshall(n, distances);

        return calculateMinimumCost(n, distances, source, target);
    }

private:

    void Floyd_Warshall(int vertex, vector<vector<int>>& distances)
    {
        for(int k=0; k <vertex; k++)
        {
            for(int i=0; i<vertex; i++)
            {
                for(int j=0; j<vertex; j++)
                {
                    if(distances[i][j]>distances[i][k]+distances[k][j])
                    {
                        distances[i][j] = distances[i][k]+distances[k][j];
                    }
                }
            }
        }
    }

    long long calculateMinimumCost(int n, vector<vector<int>>& distances, string source, string target) {
        const int INF = 1e8 + 7;
        long long minTotalCost = 0;

        for(int i=0; i<source.size(); i++) {
            int u = source[i] - 'a';
            int v = target[i] - 'a';
            if(distances[u][v] == INF) {
                return -1;
            }
            minTotalCost += distances[u][v];

        }
        return minTotalCost;
    }
};

Tags: C++, cpp, leetcode, leetcode 2976, graph, Floyd Warshall, minimum cost, directed graph