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

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 <= 2000
  • 1 <= words.length == costs.length <= 50
  • 1 <= words[i].length <= target.length
  • target and words[i] consist only of lowercase English letters.
  • 1 <= costs[i] <= 10^5

Solution

Method 1 – Dynamic Programming (Substring Matching)

Intuition

We want to build the target string by appending words from the list, minimizing the total cost. Since the constraints are small, we can use a simple DP where for each position, we check all words that could end at that position and update the minimum cost.

Approach

  1. Let dp[i] be the minimum cost to build target[:i]. Initialize dp[0] = 0, others to infinity.
  2. For each position i in target (1 to n):
    • For each word, if target[i-len(word):i] == word, update dp[i] = min(dp[i], dp[i-len(word)] + cost).
  3. 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

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;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < words.size(); ++j) {
                int m = words[j].size();
                if (i >= m && target.substr(i-m, m) == words[j]) {
                    dp[i] = min(dp[i], dp[i-m] + costs[j]);
                }
            }
        }
        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

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
    for i := 1; i <= n; i++ {
        for j, w := range words {
            m := len(w)
            if i >= m && target[i-m:i] == w {
                if dp[i-m]+costs[j] < dp[i] {
                    dp[i] = dp[i-m] + costs[j]
                }
            }
        }
    }
    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

class Solution {
    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;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < words.length; j++) {
                int m = words[j].length();
                if (i >= m && target.substring(i-m, i).equals(words[j])) {
                    dp[i] = Math.min(dp[i], dp[i-m] + costs[j]);
                }
            }
        }
        return dp[n] >= 1e9 ? -1 : dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    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
        for (i in 1..n) {
            for (j in words.indices) {
                val m = words[j].length
                if (i >= m && target.substring(i-m, i) == words[j]) {
                    dp[i] = minOf(dp[i], dp[i-m] + costs[j])
                }
            }
        }
        return if (dp[n] >= 1_000_000_000) -1 else dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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
        for i in range(1, n+1):
            for w, c in zip(words, costs):
                m = len(w)
                if i >= m and target[i-m:i] == w:
                    dp[i] = min(dp[i], dp[i-m] + c)
        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

impl Solution {
    pub fn minimum_cost(target: String, words: Vec<String>, costs: Vec<i32>) -> i32 {
        let n = target.len();
        let t = target.as_bytes();
        let mut dp = vec![i32::MAX; n+1];
        dp[0] = 0;
        for i in 1..=n {
            for (w, &c) in words.iter().zip(costs.iter()) {
                let m = w.len();
                if i >= m && &t[i-m..i] == w.as_bytes() {
                    dp[i] = dp[i].min(dp[i-m] + c);
                }
            }
        }
        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

class Solution {
    minimumCost(target: string, words: string[], costs: number[]): number {
        const n = target.length;
        const dp = Array(n+1).fill(Infinity);
        dp[0] = 0;
        for (let i = 1; i <= n; i++) {
            for (let j = 0; j < words.length; j++) {
                const m = words[j].length;
                if (i >= m && target.slice(i-m, i) === words[j]) {
                    dp[i] = Math.min(dp[i], dp[i-m] + costs[j]);
                }
            }
        }
        return dp[n] === Infinity ? -1 : dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n * W * L), where n is the length of target, W is the number of words, and L is the average word length. For each position, we check all words.
  • 🧺 Space complexity: O(n), for the DP array.