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#
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#
Cpp
Go
Java
Kotlin
Python
Rust
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
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).