3253. Construct String with Minimum Cost (Easy) 🔒

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 <= 2000
• 1 <= words.length == costs.length <= 50
• 1 <= words[i].length <= target.length
• target and words[i] consist only of lowercase English letters.
• 1 <= costs[i] <= 105

Solutions

Solution 1: Trie + Memoized Search

We first create a Trie $\textit{trie}$, where each node in the Trie contains an array $\textit{children}$ of length $26$, and each element in the array is a pointer to the next node. Each node in the Trie also contains a $\textit{cost}$ variable, which represents the minimum cost from the root node to the current node.

We traverse the $\textit{words}$ array, inserting each word into the Trie while updating the $\textit{cost}$ variable for each node.

Next, we define a memoized search function $\textit{dfs}(i)$, which represents the minimum cost to construct the string starting from $\textit{target}[i]$. The answer is $\textit{dfs}(0)$.

The calculation process of the function $\textit{dfs}(i)$ is as follows:

• If $i \geq \textit{len}(\textit{target})$, it means the entire string has been constructed, so return $0$.
• Otherwise, we start from the root node of the $\textit{trie}$ and traverse all suffixes starting from $\textit{target}[i]$, finding the minimum cost, which is the $\textit{cost}$ variable in the $\textit{trie}$, plus the result of $\textit{dfs}(j+1)$, where $j$ is the ending position of the suffix starting from $\textit{target}[i]$.

Finally, if $\textit{dfs}(0) < \textit{inf}$, return $\textit{dfs}(0)$; otherwise, return $-1$.

The time complexity is $O(n^2 + L)$, and the space complexity is $O(n + L)$. Here, $n$ is the length of $\textit{target}$, and $L$ is the sum of the lengths of all words in the $\textit{words}$ array.

Python3JavaC++GoTypeScript

class Trie:
    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26
        self.cost = inf

    def insert(self, word: str, cost: int):
        node = self
        for c in word:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.cost = min(node.cost, cost)


class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(target):
                return 0
            ans = inf
            node = trie
            for j in range(i, len(target)):
                idx = ord(target[j]) - ord("a")
                if node.children[idx] is None:
                    return ans
                node = node.children[idx]
                ans = min(ans, node.cost + dfs(j + 1))
            return ans

        trie = Trie()
        for word, cost in zip(words, costs):
            trie.insert(word, cost)
        ans = dfs(0)
        return ans if ans < inf else -1

class Trie {
    public final int inf = 1 << 29;
    public Trie[] children = new Trie[26];
    public int cost = inf;

    public void insert(String word, int cost) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.cost = Math.min(node.cost, cost);
    }
}

class Solution {
    private Trie trie = new Trie();
    private char[] target;
    private Integer[] f;

    public int minimumCost(String target, String[] words, int[] costs) {
        for (int i = 0; i < words.length; ++i) {
            trie.insert(words[i], costs[i]);
        }
        this.target = target.toCharArray();
        f = new Integer[target.length()];
        int ans = dfs(0);
        return ans < trie.inf ? ans