2976. Minimum Cost to Convert String I

Problem Description

You have two strings, source and target, which are both of the same length n and consist of lowercase English letters. Additionally, you're provided with two character arrays, original and changed, as well as an integer array cost. Each element in these arrays represents a potential character transformation from original[i] to changed[i] at the given cost[i].

Your task is to transform the source string into the target string. For each character in source that needs to be changed, you can change it into another character using one of the transformations given in the original, changed, and cost arrays. The goal is to achieve this transformation at the minimum total cost. If no sequence of transformations can convert source to target, you should return -1.

Remember that multiple entries in original and changed can represent the same character transformation but might have different costs. You always want to choose the least expensive option for every single character change.

Intuition

To solve this problem, we need to find the cheapest possible transformation for each character in the source string to match the target string. Since each character in source can be independently changed to any other character, this scenario is similar to finding the shortest paths in a graph, where characters are nodes and transformations are directed edges with weights equal to their costs.

For such graph problems, the Floyd-Warshall algorithm is a well-known algorithm that finds the shortest paths between all pairs of nodes in a graph, which fits our needs perfectly. By treating each of the 26 lowercase English letters as a node, we can use the algorithm to find the minimum cost to convert any letter to any other letter after considering all possible intermediate transformations.

The given solution initializes a graph of the transformations and their costs and then applies the Floyd-Warshall algorithm to this graph. After this step, the graph contains the minimum cost for changing any letter to any other directly or through a sequence of transformations.

When we iterate over the source and target strings, we check the cost of transforming each character in source to the corresponding character in target using the previously computed graph. If a transformation is impossible (signified by the cost being inf), we return -1. Otherwise, we keep a running total of the costs for each transformation. By the end of this process, we've calculated the minimum possible cost to transform the source string into the target string.

Learn more about Graph and Shortest Path patterns.

Solution Approach

The solution employs the Floyd-Warshall algorithm, which is an all-pairs shortest path algorithm, and is particularly well-suited for solving problems like our current one where we need the lowest cost to change any character into any other character. This algorithm works even if there are indirect ways of obtaining a transformation at a smaller cost through a sequence of intermediate character changes.

Here's a detailed step-by-step breakdown of the solution implementation:

1. Graph Initialization: We initialize a 2D array g with dimensions 26 x 26 to represent a graph, where the i-th row and j-th column represent the cost of transforming the i-th letter of the alphabet to the j-th letter. The array is initialized to inf to denote an initially infinite cost between any two characters. The diagonal is set to 0 since the cost of changing a letter to itself is 0.

2. Graph Construction: We iterate through the original, changed, and cost arrays simultaneously to fill in the graph with given transformation costs. When we encounter duplicate transformations, we keep the one with the lowest cost by using min(g[x][y], z).

3. Applying the Floyd-Warshall Algorithm: We run a triple nested loop (k, i, j) over all possible characters to find the shortest paths. This part updates the g array such that g[i][j] will contain the minimum cost of converting the letter i to letter j, possibly through an intermediate letter k. After Floyd-Warshall, g will reflect the cheapest cost of direct and indirect character transformations.

4. Transformation Cost Calculation: We iterate over both source and target at the same time and for each pair (a, b) of characters, we check if they need to be transformed (a != b). If they do, we retrieve the transformation cost from g. If g indicates an inf cost, this means no transformation is available and we return -1. Otherwise, we accumulate the cost of each transformation to calculate the total cost.

5. Returning the Result: Finally, if all characters have been successfully transformed or no transformation was needed, we return the accumulated cost.

In summary, this solution leverages a dynamic programming approach to comprehensively calculate the cheapest transformations between all possible pairs of characters using the Floyd-Warshall algorithm and then uses that information to determine the minimum cost of transforming source to target.

Example Walkthrough

Let's illustrate the solution approach using a simple example:

Suppose source = "abc", target = "xyz", and we have the following arrays of transformations:

• original = ['a', 'b', 'c', 'b']
• changed = ['x', 'y', 'x', 'z']
• cost = [5, 10, 7, 3]

This indicates that we can transform 'a' to 'x' at a cost of 5, 'b' to 'y' at a cost of 10, 'c' to 'x' at a cost of 7, and 'b' to 'z' at a cost of 3.

Following the steps of the solution approach:

1. Graph Initialization: We create a 2D array g with dimensions 26 x 26, representing the graph with all nodes initialized to inf, except the diagonal which is initialized to 0 since transforming a letter to itself has no cost.

2. Graph Construction: We iterate through our transformation arrays and update g with the given costs. After iterating, g looks like this (partial view):

   1(to)
   2 a   b   c   x   y   z
   3a 0  inf inf inf inf inf
   4b inf   0 inf inf  10   3
   5c inf inf   0   7 inf inf
   6x inf inf inf   0 inf inf
   7...
   8(from)

   Since we have two transformations for 'b' (to 'y' and 'z'), we keep the cheaper one: 'b' to 'z' at a cost of 3.

3. Applying the Floyd-Warshall Algorithm: We run the Floyd-Warshall algorithm, and in this small example no new paths would be found since there are no intermediate nodes that provide a shorter path. After applying the algorithm, the g array would remain unchanged.

4. Transformation Cost Calculation: We simultaneously iterate over source and target. For each character in source, we check the corresponding cost to transform it into the target character:

   • Transforming 'a' to 'x': Direct cost is 5.
   • Transforming 'b' to 'y': Since we kept the cost of 'b' to 'z' as 3 in step 2 (ignoring the cost of 10), we need to check if there's an indirect way to get from 'b' to 'y'. Since our example has no intermediate transformations that enable 'b' to 'y', we would have to consider the direct cost of 10.
   • Transforming 'c' to 'z': No direct transformation exists. If g[c][z] is still inf, this means it's not possible to transform 'c' to 'z', and we should return -1.

   In our example, transforming 'c' to 'z' directly is impossible, so we would check g[c][z]. If it's inf, then the total cost is -1 as the transformation cannot be completed. Assuming it's possible through other transformations, we would sum the costs from g.

5. Returning the Result: If the transformation of 'c' to 'z' is impossible, we return -1. Otherwise, we would return the sum of the valid transformation costs, which in our case is 5 + 10 + (cost of c to z) if g[c][z] is not inf.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down as follows:

1. Initialization of the graph: It initializes a 26x26 matrix to inf, except the diagonal which is set to 0. This initialization takes O(|\Sigma|^2) time, where |\Sigma| is the size of the alphabet (26 in this case).

2. Building the graph: Then, it iterates over the zipped original, changed, and cost arrays to update the graph. Since the arrays' size is m, this part of the process takes O(m) time.

3. Floyd-Warshall Algorithm: It uses the Floyd-Warshall algorithm to find the shortest path between all pairs of characters. The algorithm has three nested loops each running 26 times (since |\Sigma| = 26), resulting in a time complexity of O(|\Sigma|^3).

4. Calculating Minimum Cost: Finally, the code iterates over the zipped source and target strings, which in the worst case can be of length n. For each character pair, it checks and sums up the conversion costs. This takes O(n) time, assuming that the access time for each g[x][y] is O(1).

Adding all these parts gives a total time complexity O(m + n + |\Sigma|^3), as stated in the reference answer.

Space Complexity

The space complexity is dominated by the space needed for storing the graph g, which is a 26x26 matrix. Thus, the space complexity is O(|\Sigma|^2).

Here, |\Sigma| represents the size of the alphabet, and in this case, |\Sigma| = 26 as it deals with lowercase English letters. So the space complexity can be specifically stated as O(26^2) which essentially is O(1) because it remains constant regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.