3213. Construct String with Minimum Cost

Problem Link

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] 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.

 

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" 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:

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 to 5 * 104.
• target and words[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