Minimum Cost to Convert String II
Problem
You are given equal-length strings source and target, plus rules original[i] → changed[i] each with a cost[i]. A single operation replaces a substring equal to some original[i] with the matching changed[i], paying its cost; rules may be chained. Two operations must act on disjoint or identical index ranges. Return the minimum total cost to turn source into target, or -1 if impossible.
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]28def minimumCost(source, target, original, changed, cost):
INF = float('inf')
ids = {} # unique string -> id
def gid(s):
if s not in ids: ids[s] = len(ids)
return ids[s]
m = len(original)
for i in range(m): # register every endpoint
gid(original[i]); gid(changed[i])
k = len(ids)
dist = [[INF] * k for _ in range(k)] # all-pairs cheapest convert
for i in range(k): dist[i][i] = 0
for i in range(m): # seed direct edges (keep min)
u, v = ids[original[i]], ids[changed[i]]
dist[u][v] = min(dist[u][v], cost[i])
for w in range(k): # Floyd-Warshall
for i in range(k):
if dist[i][w] == INF: continue
for j in range(k):
if dist[i][w] + dist[w][j] < dist[i][j]:
dist[i][j] = dist[i][w] + dist[w][j]
lens = sorted({len(s) for s in original}) # rule lengths to try
n = len(source)
dp = [INF] * (n + 1) # dp[i]=cost for prefix len i
dp[0] = 0
for i in range(1, n + 1):
if source[i - 1] == target[i - 1] and dp[i - 1] < INF:
dp[i] = dp[i - 1] # chars match: free
for L in lens:
j = i - L
if j < 0 or dp[j] == INF: continue
a, b = source[j:i], target[j:i] # substring conversion
if a in ids and b in ids:
c = dist[ids[a]][ids[b]]
if c < INF: dp[i] = min(dp[i], dp[j] + c)
return dp[n] if dp[n] < INF else -1function minimumCost(source, target, original, changed, cost) {
const INF = Infinity, ids = new Map(); // unique string -> id
const gid = s => { if (!ids.has(s)) ids.set(s, ids.size); return ids.get(s); };
const m = original.length;
for (let i = 0; i < m; i++) { gid(original[i]); gid(changed[i]); }
const k = ids.size;
const dist = Array.from({ length: k }, () => new Array(k).fill(INF));
for (let i = 0; i < k; i++) dist[i][i] = 0;
for (let i = 0; i < m; i++) { // seed direct edges
const u = ids.get(original[i]), v = ids.get(changed[i]);
dist[u][v] = Math.min(dist[u][v], cost[i]);
}
for (let w = 0; w < k; w++) // Floyd-Warshall
for (let i = 0; i < k; i++) {
if (dist[i][w] === INF) continue;
for (let j = 0; j < k; j++)
if (dist[i][w] + dist[w][j] < dist[i][j])
dist[i][j] = dist[i][w] + dist[w][j];
}
const lens = [...new Set(original.map(s => s.length))].sort((a, b) => a - b);
const n = source.length, dp = new Array(n + 1).fill(INF);
dp[0] = 0; // dp[i]=cost for prefix i
for (let i = 1; i <= n; i++) {
if (source[i - 1] === target[i - 1] && dp[i - 1] < INF)
dp[i] = dp[i - 1]; // chars match: free
for (const L of lens) {
const j = i - L;
if (j < 0 || dp[j] === INF) continue;
const a = source.slice(j, i), b = target.slice(j, i);
if (ids.has(a) && ids.has(b)) { // substring conversion
const c = dist[ids.get(a)][ids.get(b)];
if (c < INF) dp[i] = Math.min(dp[i], dp[j] + c);
}
}
}
return dp[n] < INF ? dp[n] : -1;
}long minimumCost(String source, String target, String[] original,
String[] changed, int[] cost) {
final long INF = Long.MAX_VALUE / 4;
Map<String, Integer> ids = new HashMap<>(); // unique string -> id
for (String s : original) ids.putIfAbsent(s, ids.size());
for (String s : changed) ids.putIfAbsent(s, ids.size());
int k = ids.size(), m = original.length;
long[][] dist = new long[k][k];
for (long[] row : dist) Arrays.fill(row, INF);
for (int i = 0; i < k; i++) dist[i][i] = 0;
for (int i = 0; i < m; i++) { // seed direct edges
int u = ids.get(original[i]), v = ids.get(changed[i]);
dist[u][v] = Math.min(dist[u][v], cost[i]);
}
for (int w = 0; w < k; w++) // Floyd-Warshall
for (int i = 0; i < k; i++) {
if (dist[i][w] == INF) continue;
for (int j = 0; j < k; j++)
if (dist[i][w] + dist[w][j] < dist[i][j])
dist[i][j] = dist[i][w] + dist[w][j];
}
TreeSet<Integer> lens = new TreeSet<>();
for (String s : original) lens.add(s.length());
int n = source.length();
long[] dp = new long[n + 1];
Arrays.fill(dp, INF); dp[0] = 0; // dp[i]=cost for prefix i
for (int i = 1; i <= n; i++) {
if (source.charAt(i - 1) == target.charAt(i - 1) && dp[i - 1] < INF)
dp[i] = dp[i - 1]; // chars match: free
for (int L : lens) {
int j = i - L;
if (j < 0 || dp[j] == INF) continue;
String a = source.substring(j, i), b = target.substring(j, i);
if (ids.containsKey(a) && ids.containsKey(b)) {
long c = dist[ids.get(a)][ids.get(b)];
if (c < INF) dp[i] = Math.min(dp[i], dp[j] + c);
}
}
}
return dp[n] < INF ? dp[n] : -1;
}long long minimumCost(string source, string target, vector<string>& original,
vector<string>& changed, vector<int>& cost) {
const long long INF = LLONG_MAX / 4;
unordered_map<string, int> ids; // unique string -> id
auto gid = [&](const string& s) {
if (!ids.count(s)) ids[s] = ids.size();
return ids[s];
};
int m = original.size();
for (int i = 0; i < m; i++) { gid(original[i]); gid(changed[i]); }
int k = ids.size();
vector<vector<long long>> dist(k, vector<long long>(k, INF));
for (int i = 0; i < k; i++) dist[i][i] = 0;
for (int i = 0; i < m; i++) { // seed direct edges
int u = ids[original[i]], v = ids[changed[i]];
dist[u][v] = min(dist[u][v], (long long)cost[i]);
}
for (int w = 0; w < k; w++) // Floyd-Warshall
for (int i = 0; i < k; i++) {
if (dist[i][w] == INF) continue;
for (int j = 0; j < k; j++)
if (dist[i][w] + dist[w][j] < dist[i][j])
dist[i][j] = dist[i][w] + dist[w][j];
}
set<int> lens;
for (auto& s : original) lens.insert(s.size());
int n = source.size();
vector<long long> dp(n + 1, INF);
dp[0] = 0; // dp[i]=cost for prefix i
for (int i = 1; i <= n; i++) {
if (source[i - 1] == target[i - 1] && dp[i - 1] < INF)
dp[i] = dp[i - 1]; // chars match: free
for (int L : lens) {
int j = i - L;
if (j < 0 || dp[j] == INF) continue;
string a = source.substr(j, L), b = target.substr(j, L);
if (ids.count(a) && ids.count(b)) {
long long c = dist[ids[a]][ids[b]];
if (c < INF) dp[i] = min(dp[i], dp[j] + c);
}
}
}
return dp[n] < INF ? dp[n] : -1;
}Explanation
The disjoint-or-identical rule means each index of source belongs to at most one operation's range. So a valid plan slices source into non-overlapping pieces; each piece is either left alone (its characters already match) or converted as a whole from its source text to its target text. We want the cheapest such slicing — a classic partition DP.
Step 1 — strings as graph nodes. Give every distinct string appearing in original or changed a unique id (at most 2m of them). Each rule original[i] → changed[i] is a directed edge with weight cost[i]; if a pair repeats we keep the smaller cost.
Step 2 — cheapest conversions. Because rules can be chained (a→b then b→c), the cost of turning string x into string y is the shortest path from node x to node y. With only a few dozen nodes, Floyd–Warshall computes all-pairs shortest paths in O(k³), filling a dist table.
Step 3 — prefix DP. Let dp[i] be the minimum cost to fix the first i characters. dp[0] = 0. For each i we have two moves: if source[i-1] == target[i-1] we extend for free from dp[i-1]; and for each distinct rule length L, if the substrings source[j..i) and target[j..i) are both known strings, we may pay dist between them on top of dp[j] (where j = i - L).
Only the lengths that actually appear in original are worth testing, which keeps the inner loop tiny. The answer is dp[n], or -1 if it stayed infinite. A trie over the rule strings can replace the substring lookups for an even tighter bound, but a hash map of seen strings is enough here.
Example: "abcd" → "acbe". Position 0 matches (a=a, free). Then single-char rules give b→c (5), c→e→b (1+2=3), d→e (20), so dp[4] = 0 + 5 + 3 + 20 = 28.