3213. Construct String with Minimum Cost
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]
tos
. - The cost of operation is
costs[i]
.
Return the minimum cost to make s
equal to target
. If it's not possible, return -1
.
Example 1:
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"
tos
at a cost of 1, resulting ins = "abc"
. - Select index 2 and append
"d"
tos
at a cost of 1, resulting ins = "abcd"
. - Select index 4 and append
"ef"
tos
at a cost of 5, resulting ins = "abcdef"
.
Example 2:
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 * 104
1 <= words.length == costs.length <= 5 * 104
1 <= words[i].length <= target.length
- The total sum of
words[i].length
is less than or equal to5 * 104
. target
andwords[i]
consist only of lowercase English letters.1 <= costs[i] <= 104
Solution:
class Solution {
static class TrieNode {
TrieNode[] children;
int cost;
TrieNode() {
children = new TrieNode[26];
cost = Integer.MAX_VALUE;
}
}
public int minimumCost(String target, String[] words, int[] costs) {
TrieNode root = new TrieNode();
int n = target.length();
// Build the Trie
for (int i = 0; i < words.length; i++) {
TrieNode node = root;
for (char c : words[i].toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.cost = Math.min(node.cost, costs[i]);
}
// Initialize DP array
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
// Fill DP array using the Trie
for (int i = 0; i < n; i++) {
if (dp[i] == Integer.MAX_VALUE) continue;
TrieNode node = root;
for (int j = i; j < n; j++) {
if (node == null) break;
node = node.children[target.charAt(j) - 'a'];
if (node != null && node.cost != Integer.MAX_VALUE) {
dp[j + 1] = Math.min(dp[j + 1], dp[i] + node.cost);
}
}
}
return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
}
}