Problem

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 _theminimum cost to convert the string _source to the stringtarget usingany 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].

Examples

Example 1

1
2
3
4
5
6
7
8
9

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.

Example 2

1
2
3
4
5
6
7
8

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

1
2
3
4
5

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] <= 10^6

Solution

Method 1 – Dijkstra’s Algorithm with Trie Optimization

Intuition

We want to convert source to target using the minimum cost, where each operation can replace any substring with another at a given cost. This is similar to finding the shortest path in a graph, where each node is a string and edges are substring replacements. To efficiently find applicable substring replacements, we use a Trie to match substrings in source.

Approach

  1. Build a Trie for all original strings, storing their indices for cost lookup.
  2. Use Dijkstra’s algorithm:
    • Each state is a string and its current cost.
    • Use a min-heap to always expand the lowest-cost state.
    • For each position in the current string, use the Trie to find all possible substring replacements.
    • For each match, replace the substring, add the cost, and push the new string to the heap if it hasn’t been visited with a lower cost.
  3. Stop when the current string equals target.
  4. If not possible, return -1.

Code

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Trie {
public:
    struct Node {
        unordered_map<char, Node*> nxt;
        vector<int> idxs;
    } root;
    void insert(const string& s, int idx) {
        Node* cur = &root;
        for (char c : s) {
            if (!cur->nxt.count(c)) cur->nxt[c] = new Node();
            cur = cur->nxt[c];
        }
        cur->idxs.push_back(idx);
    }
    vector<pair<int,int>> find(const string& s, int pos) {
        vector<pair<int,int>> res;
        Node* cur = &root;
        for (int i = pos; i < s.size(); ++i) {
            if (!cur->nxt.count(s[i])) break;
            cur = cur->nxt[s[i]];
            for (int idx : cur->idxs) res.push_back({i, idx});
        }
        return res;
    }
};
class Solution {
public:
    int minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
        if (source == target) return 0;
        int n = source.size();
        Trie trie;
        for (int i = 0; i < original.size(); ++i) trie.insert(original[i], i);
        unordered_map<string, int> dist;
        priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>> pq;
        dist[source] = 0;
        pq.push({0, source});
        while (!pq.empty()) {
            auto [c, s] = pq.top(); pq.pop();
            if (c > dist[s]) continue;
            if (s == target) return c;
            for (int i = 0; i < n; ++i) {
                for (auto [j, idx] : trie.find(s, i)) {
                    string ns = s.substr(0, i) + changed[idx] + s.substr(j+1);
                    int nc = c + cost[idx];
                    if (!dist.count(ns) || nc < dist[ns]) {
                        dist[ns] = nc;
                        pq.push({nc, ns});
                    }
                }
            }
        }
        return -1;
    }
};
 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

// Trie omitted for brevity, use map for substring matching
func minimumCost(source, target string, original, changed []string, cost []int) int {
    if source == target { return 0 }
    n := len(source)
    type state struct{ s string; c int }
    dist := map[string]int{source: 0}
    pq := &heapMin{}; heap.Init(pq)
    heap.Push(pq, node{0, source})
    for pq.Len() > 0 {
        cur := heap.Pop(pq).(node)
        if cur.c > dist[cur.s] { continue }
        if cur.s == target { return cur.c }
        for i := 0; i < n; i++ {
            for idx, o := range original {
                if i+len(o) <= n && cur.s[i:i+len(o)] == o {
                    ns := cur.s[:i] + changed[idx] + cur.s[i+len(o):]
                    nc := cur.c + cost[idx]
                    if d, ok := dist[ns]; !ok || nc < d {
                        dist[ns] = nc
                        heap.Push(pq, node{nc, ns})
                    }
                }
            }
        }
    }
    return -1
}
 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
29
30

class Solution {
    public int minimumCost(String source, String target, List<String> original, List<String> changed, List<Integer> cost) {
        if (source.equals(target)) return 0;
        int n = source.length();
        Map<String, Integer> dist = new HashMap<>();
        dist.put(source, 0);
        PriorityQueue<Pair<Integer, String>> pq = new PriorityQueue<>(Comparator.comparingInt(a->a.getKey()));
        pq.offer(new Pair<>(0, source));
        while (!pq.isEmpty()) {
            Pair<Integer, String> cur = pq.poll();
            int c = cur.getKey(); String s = cur.getValue();
            if (c > dist.get(s)) continue;
            if (s.equals(target)) return c;
            for (int i = 0; i < n; ++i) {
                for (int idx = 0; idx < original.size(); ++idx) {
                    String o = original.get(idx);
                    if (i + o.length() <= n && s.substring(i, i + o.length()).equals(o)) {
                        String ns = s.substring(0, i) + changed.get(idx) + s.substring(i + o.length());
                        int nc = c + cost.get(idx);
                        if (!dist.containsKey(ns) || nc < dist.get(ns)) {
                            dist.put(ns, nc);
                            pq.offer(new Pair<>(nc, ns));
                        }
                    }
                }
            }
        }
        return -1;
    }
}
 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
29

class Solution {
    fun minimumCost(source: String, target: String, original: List<String>, changed: List<String>, cost: List<Int>): Int {
        if (source == target) return 0
        val n = source.length
        val dist = mutableMapOf<String, Int>()
        dist[source] = 0
        val pq = PriorityQueue(compareBy<Pair<Int, String>> { it.first })
        pq.add(Pair(0, source))
        while (pq.isNotEmpty()) {
            val (c, s) = pq.poll()
            if (c > dist[s]!!) continue
            if (s == target) return c
            for (i in 0 until n) {
                for (idx in original.indices) {
                    val o = original[idx]
                    if (i + o.length <= n && s.substring(i, i + o.length) == o) {
                        val ns = s.substring(0, i) + changed[idx] + s.substring(i + o.length)
                        val nc = c + cost[idx]
                        if (dist[ns] == null || nc < dist[ns]!!) {
                            dist[ns] = nc
                            pq.add(Pair(nc, ns))
                        }
                    }
                }
            }
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def minimumCost(self, source: str, target: str, original: list[str], changed: list[str], cost: list[int]) -> int:
        import heapq
        if source == target:
            return 0
        n = len(source)
        dist: dict[str, int] = {source: 0}
        pq: list[tuple[int, str]] = [(0, source)]
        while pq:
            c, s = heapq.heappop(pq)
            if c > dist[s]: continue
            if s == target: return c
            for i in range(n):
                for idx, o in enumerate(original):
                    if i + len(o) <= n and s[i:i+len(o)] == o:
                        ns = s[:i] + changed[idx] + s[i+len(o):]
                        nc = c + cost[idx]
                        if ns not in dist or nc < dist[ns]:
                            dist[ns] = nc
                            heapq.heappush(pq, (nc, ns))
        return -1
 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

impl Solution {
    pub fn minimum_cost(source: String, target: String, original: Vec<String>, changed: Vec<String>, cost: Vec<i32>) -> i32 {
        use std::collections::{BinaryHeap, HashMap};
        if source == target { return 0; }
        let n = source.len();
        let mut dist = HashMap::new();
        dist.insert(source.clone(), 0);
        let mut pq = BinaryHeap::new();
        pq.push(std::cmp::Reverse((0, source.clone())));
        while let Some(std::cmp::Reverse((c, s))) = pq.pop() {
            if let Some(&d) = dist.get(&s) { if c > d { continue; } }
            if s == target { return c; }
            for i in 0..n {
                for (idx, o) in original.iter().enumerate() {
                    if i + o.len() <= n && &s[i..i+o.len()] == o {
                        let ns = format!("{}{}{}", &s[..i], changed[idx], &s[i+o.len()..]);
                        let nc = c + cost[idx];
                        if !dist.contains_key(&ns) || nc < dist[&ns] {
                            dist.insert(ns.clone(), nc);
                            pq.push(std::cmp::Reverse((nc, ns)));
                        }
                    }
                }
            }
        }
        -1
    }
}
 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 {
    minimumCost(source: string, target: string, original: string[], changed: string[], cost: number[]): number {
        if (source === target) return 0;
        const n = source.length;
        const dist: Record<string, number> = { [source]: 0 };
        const pq: [number, string][] = [[0, source]];
        while (pq.length) {
            pq.sort((a, b) => a[0] - b[0]);
            const [c, s] = pq.shift()!;
            if (c > dist[s]) continue;
            if (s === target) return c;
            for (let i = 0; i < n; ++i) {
                for (let idx = 0; idx < original.length; ++idx) {
                    const o = original[idx];
                    if (i + o.length <= n && s.slice(i, i + o.length) === o) {
                        const ns = s.slice(0, i) + changed[idx] + s.slice(i + o.length);
                        const nc = c + cost[idx];
                        if (!(ns in dist) || nc < dist[ns]) {
                            dist[ns] = nc;
                            pq.push([nc, ns]);
                        }
                    }
                }
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(L * M * N log K) where L is the length of the string, M is the number of rules, N is the average length of original[i], and K is the number of unique strings visited.
  • 🧺 Space complexity: O(K) for the heap and visited map.