2977. Minimum Cost to Convert String II LeetCode Solution
In this guide, you will get 2977. Minimum Cost to Convert String II LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Convert String II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Cost to Convert String II
You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].
You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:
The substrings picked in the operations are source[a..b] and source[c..d] with either b < c or d < a. In other words, the indices picked in both operations are disjoint.
The substrings picked in the operations are source[a..b] and source[c..d] with a == c and b == d. In other words, the indices picked in both operations are identical.
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 “abcd” to “acbe”, do the following operations:
– Change substring source[1..1] from “b” to “c” at a cost of 5.
– Change substring source[2..2] from “c” to “e” at a cost of 1.
– Change substring source[2..2] from “e” to “b” at a cost of 2.
– Change substring source[3..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.
Input: source = “abcdefgh”, target = “acdeeghh”, original = [“bcd”,”fgh”,”thh”], changed = [“cde”,”thh”,”ghh”], cost = [1,3,5]
Output: 9
Explanation: To convert “abcdefgh” to “acdeeghh”, do the following operations:
– Change substring source[1..3] from “bcd” to “cde” at a cost of 1.
– Change substring source[5..7] from “fgh” to “thh” at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
– Change substring source[5..7] from “thh” to “ghh” at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
The total cost incurred is 1 + 3 + 5 = 9.
It can be shown that this is the minimum possible cost.
Example 3:
Input: source = “abcdefgh”, target = “addddddd”, original = [“bcd”,”defgh”], changed = [“ddd”,”ddddd”], cost = [100,1578]
Output: -1
Explanation: It is impossible to convert “abcdefgh” to “addddddd”.
If you select substring source[1..3] as the first operation to change “abcdefgh” to “adddefgh”, you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
If you select substring source[3..7] as the first operation to change “abcdefgh” to “abcddddd”, you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.
Constraints:
1 <= source.length == target.length <= 1000
source, target consist only of lowercase English characters.
1 <= cost.length == original.length == changed.length <= 100
1 <= original[i].length == changed[i].length <= source.length
original[i], changed[i] consist only of lowercase English characters.
original[i] != changed[i]
1 <= cost[i] <= 106
Complexity Analysis
Time Complexity: O(|\texttt{original}|^3 + |\texttt{source}||\texttt{original}|)
Space Complexity: O(|\texttt{original}|^2 + |\texttt{source}|)
2977. Minimum Cost to Convert String II LeetCode Solution in C++
class Solution {
public:
long long minimumCost(string source, string target, vector<string>& original,
vector<string>& changed, vector<int>& cost) {
const unordered_set<int> subLengths = getSubLengths(original);
const unordered_map<string, int> subToId = getSubToId(original, changed);
const int subCount = subToId.size();
// dist[u][v] := the minimum distance to change the substring with id u to
// the substring with id v
vector<vector<long>> dist(subCount, vector<long>(subCount, LONG_MAX));
// dp[i] := the minimum cost to change the first i letters of `source` into
// `target`, leaving the suffix untouched
vector<long> dp(source.length() + 1, LONG_MAX);
for (int i = 0; i < cost.size(); ++i) {
const int u = subToId.at(original[i]);
const int v = subToId.at(changed[i]);
dist[u][v] = min(dist[u][v], static_cast<long>(cost[i]));
}
for (int k = 0; k < subCount; ++k)
for (int i = 0; i < subCount; ++i)
if (dist[i][k] < LONG_MAX)
for (int j = 0; j < subCount; ++j)
if (dist[k][j] < LONG_MAX)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
dp[0] = 0;
for (int i = 0; i < source.length(); ++i) {
if (dp[i] == LONG_MAX)
continue;
if (target[i] == source[i])
dp[i + 1] = min(dp[i + 1], dp[i]);
for (const int subLength : subLengths) {
if (i + subLength > source.length())
continue;
const string subSource = source.substr(i, subLength);
const string subTarget = target.substr(i, subLength);
if (!subToId.contains(subSource) || !subToId.contains(subTarget))
continue;
const int u = subToId.at(subSource);
const int v = subToId.at(subTarget);
if (dist[u][v] < LONG_MAX)
dp[i + subLength] = min(dp[i + subLength], dp[i] + dist[u][v]);
}
}
return dp[source.length()] == LONG_MAX ? -1 : dp[source.length()];
}
private:
unordered_map<string, int> getSubToId(const vector<string>& original,
const vector<string>& changed) {
unordered_map<string, int> subToId;
for (const string& s : original)
if (!subToId.contains(s))
subToId[s] = subToId.size();
for (const string& s : changed)
if (!subToId.contains(s))
subToId[s] = subToId.size();
return subToId;
}
unordered_set<int> getSubLengths(const vector<string>& original) {
unordered_set<int> subLengths;
for (const string& s : original)
subLengths.insert(s.length());
return subLengths;
}
}; /* code provided by PROGIEZ */
2977. Minimum Cost to Convert String II LeetCode Solution in Java
class Solution {
public long minimumCost(String source, String target, String[] original, String[] changed,
int[] cost) {
Set<Integer> subLengths = getSubLengths(original);
Map<String, Integer> subToId = getSubToId(original, changed);
final int subCount = subToId.size();
// dist[u][v] := the minimum distance to change the substring with id u to
// the substring with id v
long[][] dist = new long[subCount][subCount];
Arrays.stream(dist).forEach(A -> Arrays.fill(A, Long.MAX_VALUE));
// dp[i] := the minimum cost to change the first i letters of `source` into
// `target`, leaving the suffix untouched
long[] dp = new long[source.length() + 1];
Arrays.fill(dp, Long.MAX_VALUE);
for (int i = 0; i < cost.length; ++i) {
final int u = subToId.get(original[i]);
final int v = subToId.get(changed[i]);
dist[u][v] = Math.min(dist[u][v], (long) cost[i]);
}
for (int k = 0; k < subCount; ++k)
for (int i = 0; i < subCount; ++i)
if (dist[i][k] < Long.MAX_VALUE)
for (int j = 0; j < subCount; ++j)
if (dist[k][j] < Long.MAX_VALUE)
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
dp[0] = 0;
for (int i = 0; i < source.length(); ++i) {
if (dp[i] == Long.MAX_VALUE)
continue;
if (target.charAt(i) == source.charAt(i))
dp[i + 1] = Math.min(dp[i + 1], dp[i]);
for (int subLength : subLengths) {
if (i + subLength > source.length())
continue;
String subSource = source.substring(i, i + subLength);
String subTarget = target.substring(i, i + subLength);
if (!subToId.containsKey(subSource) || !subToId.containsKey(subTarget))
continue;
final int u = subToId.get(subSource);
final int v = subToId.get(subTarget);
if (dist[u][v] < Long.MAX_VALUE)
dp[i + subLength] = Math.min(dp[i + subLength], dp[i] + dist[u][v]);
}
}
return dp[source.length()] == Long.MAX_VALUE ? -1 : dp[source.length()];
}
private Map<String, Integer> getSubToId(String[] original, String[] changed) {
Map<String, Integer> subToId = new HashMap<>();
for (final String s : original)
subToId.putIfAbsent(s, subToId.size());
for (final String s : changed)
subToId.putIfAbsent(s, subToId.size());
return subToId;
}
private Set<Integer> getSubLengths(String[] original) {
Set<Integer> subLengths = new HashSet<>();
for (final String s : original)
subLengths.add(s.length());
return subLengths;
}
} // code provided by PROGIEZ
2977. Minimum Cost to Convert String II LeetCode Solution in Python
class Solution:
def minimumCost(
self,
source: str,
target: str,
original: list[str],
changed: list[str],
cost: list[int],
) -> int:
subLengths = set(len(s) for s in original)
subToId = self._getSubToId(original, changed)
subCount = len(subToId)
# dist[u][v] := the minimum distance to change the substring with id u to
# the substring with id v
dist = [[math.inf for _ in range(subCount)] for _ in range(subCount)]
# dp[i] := the minimum cost to change the first i letters of `source` into
# `target`, leaving the suffix untouched
dp = [math.inf for _ in range(len(source) + 1)]
for a, b, c in zip(original, changed, cost):
u = subToId[a]
v = subToId[b]
dist[u][v] = min(dist[u][v], c)
for k in range(subCount):
for i in range(subCount):
if dist[i][k] < math.inf:
for j in range(subCount):
if dist[k][j] < math.inf:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
dp[0] = 0
for i, (s, t) in enumerate(zip(source, target)):
if dp[i] == math.inf:
continue
if s == t:
dp[i + 1] = min(dp[i + 1], dp[i])
for subLength in subLengths:
if i + subLength > len(source):
continue
subSource = source[i:i + subLength]
subTarget = target[i:i + subLength]
if subSource not in subToId or subTarget not in subToId:
continue
u = subToId[subSource]
v = subToId[subTarget]
if dist[u][v] != math.inf:
dp[i + subLength] = min(dp[i + subLength], dp[i] + dist[u][v])
return -1 if dp[len(source)] == math.inf else dp[len(source)]
def _getSubToId(self, original: str, changed: str) -> dict[str, int]:
subToId = {}
for s in original + changed:
if s not in subToId:
subToId[s] = len(subToId)
return subToId # code by PROGIEZ
