How do you solve Minimum Cost to Convert String II on LeetCode?

Minimum Cost to Convert String II (LeetCode #2977) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n^3) time complexity and O(n) space complexity. Key insight: Understanding how to represent transformations as a graph can simplify complex problems.

What is the brute force solution for Minimum Cost to Convert String II?

The brute force approach for Minimum Cost to Convert String II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach tries every possible combination of substring replacements to convert the source string to the target string. It checks all possible substrings and calculates the total cost for each valid transformation. The optimal Optimal Solution approach improves this to O(n^3).

What are the interview tips for Minimum Cost to Convert String II?

Clarify the problem requirements and constraints before diving into coding. Think about edge cases and how they might affect your solution. Discuss your thought process and approach with the interviewer.

What are common mistakes when solving Minimum Cost to Convert String II?

Not considering all possible substring transformations. Failing to handle cases where transformations are impossible.

#2977

Minimum Cost to Convert String II

Hard

ArrayStringDynamic ProgrammingGraph TheoryTrieShortest PathHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n^3)
Space	O(1)	O(n)

💡

Intuition

Time O(n^3)Space O(n)

The optimal solution uses a dynamic programming approach combined with a graph representation of the transformations. By precomputing the minimum costs between all unique transformations, we can efficiently calculate the minimum cost to convert the source to the target.

⚙️

Algorithm

3 steps

1Step 1: Create a mapping of unique strings in original and changed to unique IDs.
2Step 2: Use the Floyd-Warshall algorithm to compute the minimum costs between all pairs of unique strings.
3Step 3: Use dynamic programming to calculate the minimum cost to convert the source to the target using the precomputed costs.

solution.py28 lines

1# Full working Python code
2import numpy as np
3
4def min_cost_optimal(source, target, original, changed, cost):
5    unique = list(set(original + changed))
6    id_map = {s: i for i, s in enumerate(unique)}
7    n = len(unique)
8    dp = np.full((n, n), float('inf'))
9
10    for i in range(len(original)):
11        dp[id_map[original[i]]][id_map[changed[i]]] = min(dp[id_map[original[i]]][id_map[changed[i]]], cost[i])
12
13    for k in range(n):
14        for i in range(n):
15            for j in range(n):
16                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
17
18    total_cost = 0
19    for i in range(len(source)):
20        if source[i] != target[i]:
21            src_id = id_map[source[i]]
22            tgt_id = id_map[target[i]]
23            if dp[src_id][tgt_id] == float('inf'):
24                return -1
25            total_cost += dp[src_id][tgt_id]
26
27    return total_cost
28

ℹ

Complexity note: The complexity arises from the Floyd-Warshall algorithm which computes the shortest paths between all pairs of nodes, leading to O(n^3) time complexity.

1Understanding how to represent transformations as a graph can simplify complex problems.
2Dynamic programming can help optimize the search for minimum costs.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.