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.