Problem

You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length.

Imagine an empty string s.

You can perform the following operation any number of times (including zero):

  • Choose an index i in the range [0, words.length - 1].
  • Append words[i] to s.
  • The cost of operation is costs[i].

Return the minimum cost to make s equal to target. If it’s not possible, return -1.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: target = "abcdef", words = ["abdef","abc","d","def","ef"], costs =
[100,1,1,10,5]

Output: 7

Explanation:

The minimum cost can be achieved by performing the following operations:
  * Select index 1 and append `"abc"` to `s` at a cost of 1, resulting in `s = "abc"`.
  * Select index 2 and append `"d"` to `s` at a cost of 1, resulting in `s = "abcd"`.
  * Select index 4 and append `"ef"` to `s` at a cost of 5, resulting in `s = "abcdef"`.

Example 2

1
2
3
4

Input: target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]
Output: -1
Explanation:
It is impossible to make `s` equal to `target`, so we return -1.

Constraints

  • 1 <= target.length <= 5 * 10^4
  • 1 <= words.length == costs.length <= 5 * 10^4
  • 1 <= words[i].length <= target.length
  • The total sum of words[i].length is less than or equal to 5 * 10^4.
  • target and words[i] consist only of lowercase English letters.
  • 1 <= costs[i] <= 10^4

Solution

Method 1 – Dynamic Programming with Trie (Suffix Optimization)

Intuition

We want to build the target string by appending words from the list, minimizing the total cost. This is a classic DP problem, but to efficiently check if a word matches a suffix of the current target prefix, we use a Trie (built from reversed words). This allows us to check all possible word endings at each position efficiently.

Approach

  1. Build a Trie from the reversed words array, storing the cost for each word at the end node.
  2. Let dp[i] be the minimum cost to build target[:i]. Initialize dp[0] = 0, others to infinity.
  3. For each position i in target (1 to n):
    • Walk backwards in target, following the Trie, and for each match, update dp[i] = min(dp[i], dp[j] + cost) where j is the start of the matched word.
  4. The answer is dp[n] if it is not infinity, else -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

class Trie {
public:
    struct Node {
        vector<Node*> next;
        int cost;
        Node() : next(26, nullptr), cost(-1) {}
    };
    Node* root;
    Trie() { root = new Node(); }
    void insert(const string& w, int c) {
        Node* node = root;
        for (int i = w.size()-1; i >= 0; --i) {
            int idx = w[i] - 'a';
            if (!node->next[idx]) node->next[idx] = new Node();
            node = node->next[idx];
        }
        node->cost = c;
    }
};
class Solution {
public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        int n = target.size();
        vector<int> dp(n+1, 1e9);
        dp[0] = 0;
        Trie trie;
        for (int i = 0; i < words.size(); ++i) trie.insert(words[i], costs[i]);
        for (int i = 1; i <= n; ++i) {
            Trie::Node* node = trie.root;
            for (int j = i-1; j >= 0; --j) {
                int idx = target[j] - 'a';
                if (!node->next[idx]) break;
                node = node->next[idx];
                if (node->cost != -1) dp[i] = min(dp[i], dp[j] + node->cost);
            }
        }
        return dp[n] >= 1e9 ? -1 : dp[n];
    }
};
 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

func MinimumCost(target string, words []string, costs []int) int {
    n := len(target)
    dp := make([]int, n+1)
    for i := range dp { dp[i] = 1e9 }
    dp[0] = 0
    type Node struct {
        next [26]*Node
        cost int
    }
    root := &Node{cost: -1}
    for i, w := range words {
        node := root
        for j := len(w)-1; j >= 0; j-- {
            idx := w[j] - 'a'
            if node.next[idx] == nil { node.next[idx] = &Node{cost: -1} }
            node = node.next[idx]
        }
        node.cost = costs[i]
    }
    for i := 1; i <= n; i++ {
        node := root
        for j := i-1; j >= 0; j-- {
            idx := target[j] - 'a'
            if node.next[idx] == nil { break }
            node = node.next[idx]
            if node.cost != -1 && dp[j]+node.cost < dp[i] {
                dp[i] = dp[j] + node.cost
            }
        }
    }
    if dp[n] >= 1e9 { return -1 }
    return dp[n]
}
 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

class Solution {
    static class Node {
        Node[] next = new Node[26];
        int cost = -1;
    }
    public int minimumCost(String target, String[] words, int[] costs) {
        int n = target.length();
        int[] dp = new int[n+1];
        Arrays.fill(dp, (int)1e9);
        dp[0] = 0;
        Node root = new Node();
        for (int i = 0; i < words.length; i++) {
            Node node = root;
            String w = words[i];
            for (int j = w.length()-1; j >= 0; j--) {
                int idx = w.charAt(j) - 'a';
                if (node.next[idx] == null) node.next[idx] = new Node();
                node = node.next[idx];
            }
            node.cost = costs[i];
        }
        for (int i = 1; i <= n; i++) {
            Node node = root;
            for (int j = i-1; j >= 0; j--) {
                int idx = target.charAt(j) - 'a';
                if (node.next[idx] == null) break;
                node = node.next[idx];
                if (node.cost != -1) dp[i] = Math.min(dp[i], dp[j] + node.cost);
            }
        }
        return dp[n] >= 1e9 ? -1 : dp[n];
    }
}
 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

class Solution {
    class Node {
        val next = Array<Node?>(26) { null }
        var cost = -1
    }
    fun minimumCost(target: String, words: Array<String>, costs: IntArray): Int {
        val n = target.length
        val dp = IntArray(n+1) { 1_000_000_000 }
        dp[0] = 0
        val root = Node()
        for (i in words.indices) {
            var node = root
            for (j in words[i].length-1 downTo 0) {
                val idx = words[i][j] - 'a'
                if (node.next[idx] == null) node.next[idx] = Node()
                node = node.next[idx]!!
            }
            node.cost = costs[i]
        }
        for (i in 1..n) {
            var node = root
            for (j in i-1 downTo 0) {
                val idx = target[j] - 'a'
                if (node.next[idx] == null) break
                node = node.next[idx]!!
                if (node.cost != -1) dp[i] = minOf(dp[i], dp[j] + node.cost)
            }
        }
        return if (dp[n] >= 1_000_000_000) -1 else dp[n]
    }
}
 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

class TrieNode:
    def __init__(self):
        self.next = [None] * 26
        self.cost = -1
class Solution:
    def minimumCost(self, target: str, words: list[str], costs: list[int]) -> int:
        n = len(target)
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        root = TrieNode()
        for w, c in zip(words, costs):
            node = root
            for ch in reversed(w):
                idx = ord(ch) - ord('a')
                if not node.next[idx]:
                    node.next[idx] = TrieNode()
                node = node.next[idx]
            node.cost = c
        for i in range(1, n+1):
            node = root
            for j in range(i-1, -1, -1):
                idx = ord(target[j]) - ord('a')
                if not node.next[idx]: break
                node = node.next[idx]
                if node.cost != -1:
                    dp[i] = min(dp[i], dp[j] + node.cost)
        return -1 if dp[n] == float('inf') else dp[n]
 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

impl Solution {
    pub fn minimum_cost(target: String, words: Vec<String>, costs: Vec<i32>) -> i32 {
        let n = target.len();
        let t = target.as_bytes();
        struct Node { next: [Option<Box<Node>>; 26], cost: i32 }
        impl Node {
            fn new() -> Self { Node { next: Default::default(), cost: -1 } }
        }
        let mut root = Box::new(Node::new());
        for (w, &c) in words.iter().zip(costs.iter()) {
            let mut node = &mut root;
            for &b in w.as_bytes().iter().rev() {
                let idx = (b - b'a') as usize;
                node = node.next[idx].get_or_insert_with(|| Box::new(Node::new()));
            }
            node.cost = c;
        }
        let mut dp = vec![i32::MAX; n+1];
        dp[0] = 0;
        for i in 1..=n {
            let mut node = &root;
            for j in (0..i).rev() {
                let idx = (t[j] - b'a') as usize;
                if node.next[idx].is_none() { break; }
                node = node.next[idx].as_ref().unwrap();
                if node.cost != -1 {
                    dp[i] = dp[i].min(dp[j] + node.cost);
                }
            }
        }
        if dp[n] == i32::MAX { -1 } else { dp[n] }
    }
}
 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

class TrieNode {
    next: (TrieNode | null)[] = Array(26).fill(null);
    cost: number = -1;
}
class Solution {
    minimumCost(target: string, words: string[], costs: number[]): number {
        const n = target.length;
        const dp = Array(n+1).fill(Infinity);
        dp[0] = 0;
        const root = new TrieNode();
        for (let i = 0; i < words.length; i++) {
            let node = root;
            for (let j = words[i].length-1; j >= 0; j--) {
                const idx = words[i].charCodeAt(j) - 97;
                if (!node.next[idx]) node.next[idx] = new TrieNode();
                node = node.next[idx]!;
            }
            node.cost = costs[i];
        }
        for (let i = 1; i <= n; i++) {
            let node = root;
            for (let j = i-1; j >= 0; j--) {
                const idx = target.charCodeAt(j) - 97;
                if (!node.next[idx]) break;
                node = node.next[idx]!;
                if (node.cost !== -1) dp[i] = Math.min(dp[i], dp[j] + node.cost);
            }
        }
        return dp[n] === Infinity ? -1 : dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n * L), where n is the length of target and L is the maximum length of a word in words. For each position, we may check up to L characters.
  • 🧺 Space complexity: O(n + W*L), where W is the number of words and L is the maximum word length (for the DP array and Trie).