#2976

Medium

LeetCode Problem Workspace

Minimum Cost to Convert String I

This problem asks to calculate the minimum cost to convert a string from source to target using specific character transformation operations.

array string graph shortest path

Problem Statement

You are given two strings, source and target, both of length n. Along with them, you are provided two character arrays original and changed, and an integer array cost. Each index i in cost represents the cost of changing original[i] to changed[i]. You can perform operations where a character in the source string can be changed to another character at the specified cost if there exists a corresponding original-to-changed pair.

Your goal is to determine the minimum cost to convert the source string into the target string, utilizing the allowed transformations. If it's impossible to convert source to target, return -1. Consider that only the exact allowed transformations, as defined by the original and changed arrays, can be used.

Examples

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

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

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

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 <= 105
source, target consist of lowercase English letters.
1 <= cost.length == original.length == changed.length <= 2000
original[i], changed[i] are lowercase English letters.
1 <= cost[i] <= 106
original[i] != changed[i]

Solution Approach

Graph Representation

The problem can be viewed as a graph traversal task. Each character in the alphabet is treated as a node, and edges are formed between characters that can be transformed with a specified cost. The task becomes finding the minimum path cost to convert characters from source to target using this graph.

Breadth-First Search (BFS)

BFS can be used to explore all valid transformations, ensuring the minimum cost is found. By considering each character in the source string as a node, BFS explores all possible transformations to determine the lowest total cost to convert the entire string.

Handling Impossible Transformations

If any character in the source string cannot be transformed to the corresponding character in the target string (i.e., no valid transformation exists), the function should immediately return -1. This requires checking for every character conversion possibility before calculating the total cost.

Complexity Analysis

Metric	Value
Time	O(m + n)
Space	O(1)

The time complexity of this solution is O(m + n), where m is the number of allowed transformations and n is the length of the source and target strings. The space complexity is O(1) as we only store information relevant to the graph representation and the cost calculations.

What Interviewers Usually Probe

Tests the candidate's ability to represent transformations as a graph.
Evaluates the ability to apply BFS for shortest path or cost calculations.
Assesses how the candidate handles edge cases, such as impossible transformations.

Common Pitfalls or Variants

Common pitfalls

Overlooking characters in the source that cannot be transformed to the target.
Incorrectly calculating the cost for a transformation that uses multiple steps.
Not correctly handling the case where no transformation exists between certain characters.

Follow-up variants

Add constraints that limit the number of transformations available.
Consider dynamic programming approaches for optimizing the cost calculation.
Introduce the possibility of multiple possible transformations between characters.

FAQ

What is the primary pattern in the Minimum Cost to Convert String I problem?

The problem primarily involves the Array plus String pattern, where transformations between characters are modeled as a graph traversal problem.

How does BFS help in solving the problem?

BFS ensures that the minimum transformation cost is found by exploring all possible transformations in the graph, starting from the source string.

What should I do if a character cannot be transformed in the problem?

If any character cannot be transformed from source to target, return -1, as the transformation is impossible.

Can this problem be solved using a greedy approach?

A greedy approach may not guarantee the minimum cost for all cases, as some transformations require multiple steps. Graph-based methods like BFS are more effective.

What is the time complexity of this problem?

The time complexity of this solution is O(m + n), where m is the number of transformations and n is the length of the strings.

terminal

Solution

Solution 1: Floyd Algorithm

According to the problem description, we can consider each letter as a node, and the conversion cost between each pair of letters as a directed edge. We first initialize a $26 \times 26$ two-dimensional array $g$, where $g[i][j]$ represents the minimum cost of converting letter $i$ to letter $j$. Initially, $g[i][j] = \infty$, and if $i = j$, then $g[i][j] = 0$.

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

class Solution:
    def minimumCost(
        self,
        source: str,
        target: str,
        original: List[str],
        changed: List[str],
        cost: List[int],
    ) -> int:
        g = [[inf] * 26 for _ in range(26)]
        for i in range(26):
            g[i][i] = 0
        for x, y, z in zip(original, changed, cost):
            x = ord(x) - ord('a')
            y = ord(y) - ord('a')
            g[x][y] = min(g[x][y], z)
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j])
        ans = 0
        for a, b in zip(source, target):
            if a != b:
                x, y = ord(a) - ord('a'), ord(b) - ord('a')
                if g[x][y] >= inf:
                    return -1
                ans += g[x][y]
        return ans

Continue Practicing

#2977 minimum cost to convert string ii #3112 minimum time to visit disappearing nodes #3286 find a safe walk through a grid