| comments | difficulty | edit_url |
|---|---|---|
true |
中等 |
给你一个字符串 target、一个字符串数组 words 以及一个整数数组 costs，这两个数组长度相同。
设想一个空字符串 s。
你可以执行以下操作任意次数（包括 零 次）：
- 选择一个在范围
[0, words.length - 1]的索引i。 - 将
words[i]追加到s。 - 该操作的成本是
costs[i]。
返回使 s 等于 target 的 最小 成本。如果不可能，返回 -1。
示例 1：
输入： target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]
输出： 7
解释：
- 选择索引 1 并以成本 1 将
"abc"追加到s，得到s = "abc"。 - 选择索引 2 并以成本 1 将
"d"追加到s，得到s = "abcd"。 - 选择索引 4 并以成本 5 将
"ef"追加到s，得到s = "abcdef"。
示例 2：
输入： target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]
输出： -1
解释：
无法使 s 等于 target，因此返回 -1。
提示：
1 <= target.length <= 20001 <= words.length == costs.length <= 501 <= words[i].length <= target.lengthtarget和words[i]仅由小写英文字母组成。1 <= costs[i] <= 105
我们首先创建一个字典树
我们遍历
接下来，我们定义一个记忆化搜索函数
函数
- 如果
$i \geq \textit{len}(\textit{target})$ ，表示已经构造完整个字符串，返回$0$ 。 - 否则，我们从
$\textit{trie}$ 的根节点开始，遍历$\textit{target}[i]$ 开始的所有后缀，找到最小花费，即$\textit{trie}$ 中的$\textit{cost}$ 变量，加上$\textit{dfs}(j+1)$ 的结果，其中$j$ 是$\textit{target}[i]$ 开始的后缀的结束位置。
最后，如果
时间复杂度
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 -1class 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 : -1;
}
private int dfs(int i) {
if (i >= target.length) {
return 0;
}
if (f[i] != null) {
return f[i];
}
f[i] = trie.inf;
Trie node = trie;
for (int j = i; j < target.length; ++j) {
int idx = target[j] - 'a';
if (node.children[idx] == null) {
return f[i];
}
node = node.children[idx];
f[i] = Math.min(f[i], node.cost + dfs(j + 1));
}
return f[i];
}
}const int inf = 1 << 29;
class Trie {
public:
Trie* children[26]{};
int cost = inf;
void insert(string& word, int cost) {
Trie* node = this;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) {
node->children[idx] = new Trie();
}
node = node->children[idx];
}
node->cost = min(node->cost, cost);
}
};
class Solution {
public:
int minimumCost(string target, vector<string>& words, vector<int>& costs) {
Trie* trie = new Trie();
for (int i = 0; i < words.size(); ++i) {
trie->insert(words[i], costs[i]);
}
int n = target.length();
int f[n];
memset(f, 0, sizeof(f));
auto dfs = [&](this auto&& dfs, int i) -> int {
if (i >= n) {
return 0;
}
if (f[i]) {
return f[i];
}
f[i] = inf;
Trie* node = trie;
for (int j = i; j < n; ++j) {
int idx = target[j] - 'a';
if (!node->children[idx]) {
return f[i];
}
node = node->children[idx];
f[i] = min(f[i], node->cost + dfs(j + 1));
}
return f[i];
};
int ans = dfs(0);
return ans < inf ? ans : -1;
}
};const inf = 1 << 29
type Trie struct {
children [26]*Trie
cost int
}
func NewTrie() *Trie {
return &Trie{cost: inf}
}
func (t *Trie) insert(word string, cost int) {
node := t
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = NewTrie()
}
node = node.children[idx]
}
node.cost = min(node.cost, cost)
}
func minimumCost(target string, words []string, costs []int) int {
trie := NewTrie()
for i, word := range words {
trie.insert(word, costs[i])
}
n := len(target)
f := make([]int, n)
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != 0 {
return f[i]
}
f[i] = inf
node := trie
for j := i; j < n; j++ {
idx := target[j] - 'a'
if node.children[idx] == nil {
return f[i]
}
node = node.children[idx]
f[i] = min(f[i], node.cost+dfs(j+1))
}
return f[i]
}
if ans := dfs(0); ans < inf {
return ans
}
return -1
}const inf = 1 << 29;
class Trie {
children: (Trie | null)[];
cost: number;
constructor() {
this.children = Array(26).fill(null);
this.cost = inf;
}
insert(word: string, cost: number): void {
let node: Trie = this;
for (const c of word) {
const idx = c.charCodeAt(0) - 97;
if (!node.children[idx]) {
node.children[idx] = new Trie();
}
node = node.children[idx]!;
}
node.cost = Math.min(node.cost, cost);
}
}
function minimumCost(target: string, words: string[], costs: number[]): number {
const trie = new Trie();
for (let i = 0; i < words.length; ++i) {
trie.insert(words[i], costs[i]);
}
const n = target.length;
const f: number[] = Array(n).fill(0);
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i]) {
return f[i];
}
f[i] = inf;
let node: Trie | null = trie;
for (let j = i; j < n; ++j) {
const idx = target.charCodeAt(j) - 97;
if (!node?.children[idx]) {
return f[i];
}
node = node.children[idx];
f[i] = Math.min(f[i], node!.cost + dfs(j + 1));
}
return f[i];
};
const ans = dfs(0);
return ans < inf ? ans : -1;
}