3213. 最小代价构造字符串
给你一个字符串 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 <= 5 * 10^41 <= words.length == costs.length <= 5 * 10^41 <= words[i].length <= target.length- 所有
words[i].length 的总和小于或等于 5 * 10^4
target 和 words[i] 仅由小写英文字母组成。1 <= costs[i] <= 10^4
字典树 + 记忆化搜索dp
（周赛竟然忘记“记忆操作”？？？memo[idx] = (int)res;）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Trie {
class TrieNode {
boolean end;
TrieNode[] children = new TrieNode[26];
int cost = -1;
}
TrieNode root = new TrieNode();
void insert(String word, int cost) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
int index = (int) c - 97;
if (cur.children[index] == null) {
cur.children[index] = new TrieNode();
}
cur = cur.children[index];
}
cur.end = true;
if (cur.cost != -1) cur.cost = Math.min(cur.cost, cost);
else cur.cost = cost;
}
boolean search(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
int index = (int) c - 97;
if (cur.children[index] == null) return false;
cur = cur.children[index];
}
return cur.end;
}
}
class Solution {
Trie tr = new Trie();
public int minimumCost(String target, String[] words, int[] costs) {
int n = words.length;
for (int i = 0; i < n; i++) tr.insert(words[i], costs[i]);
int memo[] = new int[target.length()];
Arrays.fill(memo, -1);
int res = dfs(0, target, memo);
return res == (int)1e9 ? -1 : res;
}
private int dfs(int idx, String target, int memo[]) {
if (idx == target.length()) return 0;
if (memo[idx] != -1) return memo[idx];
Trie.TrieNode cur = tr.root;
long res = (long)1e9;
for (int i = idx; i < target.length(); i++) {
int c = (int)target.charAt(i) - 97;
if (cur.children[c] != null) {
cur = cur.children[c];
if (cur.end) res = Math.min(res, dfs(i+1, target, memo) + cur.cost);
}
else break;
}
memo[idx] = (int)res;
return (int)res;
}
}
|
字符串哈希 + dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public int minimumCost(String target, String[] words, int[] costs) {
char[] t = target.toCharArray();
int n = t.length;
final int MOD = 1_070_777_777;
final int BASE = (int) 8e8 + new Random().nextInt((int) 1e8);
int[] powBase = new int[n + 1];
int[] preHash = new int[n + 1];
powBase[0] = 1;
for (int i = 0; i < n; i++) {
powBase[i + 1] = (int) ((long) powBase[i] * BASE % MOD);
preHash[i + 1] = (int) (((long) preHash[i] * BASE + t[i]) % MOD);
}
Map<Integer, Map<Integer, Integer>> minCost = new TreeMap<>();
for (int i = 0; i < words.length; i++) {
long h = 0;
for (char b : words[i].toCharArray()) {
h = (h * BASE + b) % MOD;
}
minCost.computeIfAbsent(words[i].length(), k -> new HashMap<>())
.merge((int) h, costs[i], Integer::min);
}
int[] f = new int[n + 1];
Arrays.fill(f, Integer.MAX_VALUE / 2);
f[0] = 0;
for (int i = 1; i <= n; i++) {
for (Map.Entry<Integer, Map<Integer, Integer>> e : minCost.entrySet()) {
int len = e.getKey();
if (len > i) {
break;
}
int subHash = (int) (((preHash[i] - (long) preHash[i - len] * powBase[len]) % MOD + MOD) % MOD);
f[i] = Math.min(f[i], f[i - len] + e.getValue().getOrDefault(subHash, Integer.MAX_VALUE / 2));
}
}
return f[n] == Integer.MAX_VALUE / 2 ? -1 : f[n];
}
}
|
双模字符串哈希 + dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
class Solution {
public int minimumCost(String target, String[] words, int[] costs) {
char[] t = target.toCharArray();
int n = t.length;
final int MOD1 = 1_070_777_777;
final int MOD2 = 1_000_000_007;
final int BASE1 = (int) 8e8 + new Random().nextInt((int) 1e8);
final int BASE2 = (int) 8e8 + new Random().nextInt((int) 1e8);
int[] powBase1 = new int[n + 1];
int[] powBase2 = new int[n + 1];
int[] preHash1 = new int[n + 1];
int[] preHash2 = new int[n + 1];
powBase1[0] = powBase2[0] = 1;
for (int i = 0; i < n; i++) {
powBase1[i + 1] = (int) ((long) powBase1[i] * BASE1 % MOD1);
powBase2[i + 1] = (int) ((long) powBase2[i] * BASE2 % MOD2);
preHash1[i + 1] = (int) (((long) preHash1[i] * BASE1 + t[i]) % MOD1);
preHash2[i + 1] = (int) (((long) preHash2[i] * BASE2 + t[i]) % MOD2);
}
Map<Long, Integer> minCost = new HashMap<>();
for (int i = 0; i < words.length; i++) {
long h1 = 0;
long h2 = 0;
for (char b : words[i].toCharArray()) {
h1 = (h1 * BASE1 + b) % MOD1;
h2 = (h2 * BASE2 + b) % MOD2;
}
minCost.merge(h1 << 32 | h2, costs[i], Integer::min);
}
Set<Integer> lengthSet = new HashSet<>();
for (String w : words) {
lengthSet.add(w.length());
}
int[] sortedLens = new int[lengthSet.size()];
int k = 0;
for (int len : lengthSet) {
sortedLens[k++] = len;
}
Arrays.sort(sortedLens);
int[] f = new int[n + 1];
Arrays.fill(f, Integer.MAX_VALUE / 2);
f[0] = 0;
for (int i = 1; i <= n; i++) {
for (int len : sortedLens) {
if (len > i) {
break;
}
long subHash1 = ((preHash1[i] - (long) preHash1[i - len] * powBase1[len]) % MOD1 + MOD1) % MOD1;
long subHash2 = ((preHash2[i] - (long) preHash2[i - len] * powBase2[len]) % MOD2 + MOD2) % MOD2;
long subHash = subHash1 << 32 | subHash2;
f[i] = Math.min(f[i], f[i - len] + minCost.getOrDefault(subHash, Integer.MAX_VALUE / 2));
}
}
return f[n] == Integer.MAX_VALUE / 2 ? -1 : f[n];
}
}
|
