Description
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
C++
struct TrieNode {
TrieNode *sfx = nullptr;
TrieNode *dict = nullptr;
std::array<TrieNode*, 26> child{};
int word_id = -1;
};
static TrieNode preallocated_nodes[(int)5e4 + 5];
static TrieNode *preallocated_queue[(int)5e4 + 5];
static int dp[(int)1e5 + 5];
class Solution {
public:
int minimumCost(string &target, vector<string>& words, vector<int>& costs) {
auto trie = Trie(words, costs);
int n = target.size();
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
dp[i] = 1e9;
for (int j : trie.suffixesAfterAppending(target[i - 1])) {
dp[i] = std::min(dp[i], dp[i - words[j].size()] + costs[j]);
}
}
return dp[n] == 1e9 ? -1 : dp[n];
}
struct Trie {
int count = 0;
TrieNode *newTrieNode() {
preallocated_nodes[count] = TrieNode();
return &preallocated_nodes[count++];
}
TrieNode *root = nullptr, *curr = nullptr;
Trie(vector<string>& words, vector<int> &costs) {
root = newTrieNode();
root->sfx = root->dict = root;
for (int i = 0; i < words.size(); ++i) {
auto &&word = words[i];
TrieNode *u = root;
for (auto c : word) {
if (!u->child[c - 'a']) {
u->child[c - 'a'] = newTrieNode();
}
u = u->child[c - 'a'];
}
if (u->word_id < 0 || costs[i] < costs[u->word_id]) {
u->word_id = i;
}
}
Queue q;
q.push(root);
while (!q.empty()) {
TrieNode *u = q.pop();
for (int i = 0; i < 26; ++i) {
auto v = u->child[i];
if (!v) {
continue;
}
TrieNode *p = u->sfx;
while (p != root && !p->child[i]) {
p = p->sfx;
}
if (u != root && p->child[i]) {
v->sfx = p->child[i];
} else {
v->sfx = root;
}
v->dict = v->sfx->word_id >= 0 ? v->sfx : v->sfx->dict;
q.push(v);
}
}
curr = root;
}
Trie &suffixesAfterAppending(char letter) {
while (curr != root && !curr->child[letter - 'a']) {
curr = curr->sfx;
}
if (curr->child[letter - 'a']) {
curr = curr->child[letter - 'a'];
start = curr->word_id >= 0 ? curr : curr->dict;
} else {
start = root;
}
return *this;
}
// Iterate all suffixes for current prefix, longest to shortest
TrieNode *start = root;
struct Iterator {
TrieNode *u = nullptr;
Iterator &operator++() { u = u->dict; return *this; }
bool operator==(Iterator &o) { return u == o.u; }
int operator*() { return u->word_id; }
};
Iterator begin() { return Iterator{start}; }
Iterator end() { return Iterator{root}; }
// Optimization literally just for fun
struct Queue {
int start = 0, end = 0;
inline void push(TrieNode *u) { preallocated_queue[end++] = u; }
inline TrieNode *pop() { return preallocated_queue[start++]; }
bool empty() { return start == end; }
};
};
};
Python3
class Solution:
def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
d = [{} for _ in range(max(len(x) for x in words) + 1)]
for w, c in zip(words, costs):
if w not in d[len(w)]: d[len(w)][w] = c
elif c < d[len(w)][w]: d[len(w)][w] = c
lengths = [i for i in range(len(d)) if len(d[i])]
n = len(target)
dp = [10 ** 9] * (n + 1)
dp[0] = 0
for i in range(n):
for j in lengths:
if i + j > n: break
else:
try:
cost = d[j][target[i:i+j]]
if dp[i+j] > dp[i] + cost:
dp[i+j] = dp[i] + cost
except:
pass
return dp[n] if dp[n] < 10 ** 9 else -1