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
12
13
|
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
5
6
7
8
|
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#
- Build a Trie from the reversed words array, storing the cost for each word at the end node.
- Let dp[i] be the minimum cost to build target[:i]. Initialize dp[0] = 0, others to infinity.
- 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.
- The answer is dp[n] if it is not infinity, else -1.
Code#
C++#
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]
}
|
Java#
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];
}
}
|
Kotlin#
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]
}
}
|
Python#
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]
|
Rust#
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] }
}
}
|
TypeScript#
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).