class Solution {
public:
int minimumCost(string target, vector<string>& words, vector<int>& costs) {
}
};
100350. 最小代价构造字符串
给你一个字符串 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
解释：
"abc" 追加到 s，得到 s = "abc"。"d" 追加到 s，得到 s = "abcd"。"ef" 追加到 s，得到 s = "abcdef"。示例 2：
输入： target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]
输出： -1
解释：
无法使 s 等于 target，因此返回 -1。
提示：
1 <= target.length <= 5 * 1041 <= words.length == costs.length <= 5 * 1041 <= words[i].length <= target.lengthwords[i].length 的总和小于或等于 5 * 104target 和 words[i] 仅由小写英文字母组成。1 <= costs[i] <= 104原站题解
golang 解法, 执行用时: 882 ms, 内存消耗: 211.9 MB, 提交时间: 2024-07-09 10:32:31
// golang 自带后缀数组
func minimumCost(target string, words []string, costs []int) int {
minCost := map[string]uint16{}
for i, w := range words {
c := uint16(costs[i])
if minCost[w] == 0 {
minCost[w] = c
} else {
minCost[w] = min(minCost[w], c)
}
}
n := len(target)
type pair struct{ l, cost uint16 }
from := make([][]pair, n+1)
sa := suffixarray.New([]byte(target))
for w, c := range minCost {
for _, l := range sa.Lookup([]byte(w), -1) {
r := l + len(w)
from[r] = append(from[r], pair{uint16(l), c})
}
}
f := make([]int, n+1)
for i := 1; i <= n; i++ {
f[i] = math.MaxInt / 2
for _, p := range from[i] {
f[i] = min(f[i], f[p.l]+int(p.cost))
}
}
if f[n] == math.MaxInt/2 {
return -1
}
return f[n]
}
golang 解法, 执行用时: 477 ms, 内存消耗: 9.3 MB, 提交时间: 2024-07-09 10:32:07
func minimumCost(target string, words []string, costs []int) int {
n := len(target)
// 多项式字符串哈希（方便计算子串哈希值）
// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
const mod = 1_070_777_777
base := 9e8 - rand.Intn(1e8) // 随机 base，防止 hack（注意 Go1.20 之后的版本，每次随机的数都不一样）
powBase := make([]int, n+1) // powBase[i] = base^i
preHash := make([]int, n+1) // 前缀哈希值 preHash[i] = hash(s[:i])
powBase[0] = 1
for i, b := range target {
powBase[i+1] = powBase[i] * base % mod
preHash[i+1] = (preHash[i]*base + int(b)) % mod // 秦九韶算法计算多项式哈希
}
// 计算子串 s[l:r] 的哈希值，注意这是左闭右开区间 [l,r)
// 计算方法类似前缀和
subHash := func(l, r int) int {
return ((preHash[r]-preHash[l]*powBase[r-l])%mod + mod) % mod
}
minCost := make([]map[int]int, n+1) // [words[i] 的长度][words[i] 的哈希值] -> 最小成本
lens := map[int]struct{}{} // 所有 words[i] 的长度集合
for i, w := range words {
m := len(w)
lens[m] = struct{}{}
// 计算 w 的哈希值
h := 0
for _, b := range w {
h = (h*base + int(b)) % mod
}
if minCost[m] == nil {
minCost[m] = map[int]int{}
}
if minCost[m][h] == 0 {
minCost[m][h] = costs[i]
} else {
minCost[m][h] = min(minCost[m][h], costs[i])
}
}
// 有 O(√L) 个不同的长度
sortedLens := make([]int, 0, len(lens))
for l := range lens {
sortedLens = append(sortedLens, l)
}
slices.Sort(sortedLens)
f := make([]int, n+1)
for i := 1; i <= n; i++ {
f[i] = math.MaxInt / 2
for _, sz := range sortedLens {
if sz > i {
break
}
if cost, ok := minCost[sz][subHash(i-sz, i)]; ok {
f[i] = min(f[i], f[i-sz]+cost)
}
}
}
if f[n] == math.MaxInt/2 {
return -1
}
return f[n]
}
golang 解法, 执行用时: 729 ms, 内存消耗: 9.4 MB, 提交时间: 2024-07-09 10:31:56
func minimumCost(target string, words []string, costs []int) int {
n := len(target)
// 多项式字符串哈希（方便计算子串哈希值）
// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
const mod = 1_070_777_777
base := 9e8 - rand.Intn(1e8) // 随机 base，防止 hack（注意 Go1.20 之后的版本，每次随机的数都不一样）
powBase := make([]int, n+1) // powBase[i] = base^i
preHash := make([]int, n+1) // 前缀哈希值 preHash[i] = hash(s[:i])
powBase[0] = 1
for i, b := range target {
powBase[i+1] = powBase[i] * base % mod
preHash[i+1] = (preHash[i]*base + int(b)) % mod // 秦九韶算法计算多项式哈希
}
// 计算子串 s[l:r] 的哈希值，注意这是左闭右开区间 [l,r)
// 计算方法类似前缀和
subHash := func(l, r int) int {
return ((preHash[r]-preHash[l]*powBase[r-l])%mod + mod) % mod
}
minCost := map[int]int{} // words[i] 的哈希值 -> 最小成本
lens := map[int]struct{}{} // 所有 words[i] 的长度集合
for i, w := range words {
lens[len(w)] = struct{}{}
h := 0
for _, b := range w {
h = (h*base + int(b)) % mod
}
if minCost[h] == 0 {
minCost[h] = costs[i]
} else {
minCost[h] = min(minCost[h], costs[i])
}
}
// 有 O(√L) 个不同的长度
sortedLens := make([]int, 0, len(lens))
for l := range lens {
sortedLens = append(sortedLens, l)
}
slices.Sort(sortedLens)
f := make([]int, n+1)
for i := 1; i <= n; i++ {
f[i] = math.MaxInt / 2
for _, sz := range sortedLens {
if sz > i {
break
}
if cost, ok := minCost[subHash(i-sz, i)]; ok {
f[i] = min(f[i], f[i-sz]+cost)
}
}
}
if f[n] == math.MaxInt/2 {
return -1
}
return f[n]
}
cpp 解法, 执行用时: 1462 ms, 内存消耗: 80.5 MB, 提交时间: 2024-07-09 10:31:37
class Solution {
public:
int minimumCost(string target, vector<string>& words, vector<int>& costs) {
int n = target.length();
// 多项式字符串哈希（方便计算子串哈希值）
// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
const int MOD = 1'070'777'777;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int BASE = uniform_int_distribution<>(8e8, 9e8)(rng); // 随机 base，防止 hack
vector<int> pow_base(n + 1); // pow_base[i] = base^i
vector<int> pre_hash(n + 1); // 前缀哈希值 pre_hash[i] = hash(s[:i])
pow_base[0] = 1;
for (int i = 0; i < n; i++) {
pow_base[i + 1] = (long long) pow_base[i] * BASE % MOD;
pre_hash[i + 1] = ((long long) pre_hash[i] * BASE + target[i]) % MOD; // 秦九韶算法计算多项式哈希
}
// 计算 target[l] 到 target[r-1] 的哈希值
auto sub_hash = [&](int l, int r) {
return ((pre_hash[r] - (long long) pre_hash[l] * pow_base[r - l]) % MOD + MOD) % MOD;
};
map<int, unordered_map<int, int>> min_cost; // 长度 -> 哈希值 -> 最小成本
for (int i = 0; i < words.size(); i++) {
long long h = 0;
for (char b : words[i]) {
h = (h * BASE + b) % MOD;
}
int m = words[i].length();
if (min_cost[m].find(h) == min_cost[m].end()) {
min_cost[m][h] = costs[i];
} else {
min_cost[m][h] = min(min_cost[m][h], costs[i]);
}
}
vector<int> f(n + 1, INT_MAX / 2);
f[0] = 0;
for (int i = 1; i <= n; i++) {
for (auto& [len, mc] : min_cost) {
if (len > i) {
break;
}
auto it = mc.find(sub_hash(i - len, i));
if (it != mc.end()) {
f[i] = min(f[i], f[i - len] + it->second);
}
}
}
return f[n] == INT_MAX / 2 ? -1 : f[n];
}
};
java 解法, 执行用时: 1335 ms, 内存消耗: 53.7 MB, 提交时间: 2024-07-09 10:31:20
class Solution {
public int minimumCost(String target, String[] words, int[] costs) {
char[] t = target.toCharArray();
int n = t.length;
// 多项式字符串哈希（方便计算子串哈希值）
// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
final int MOD = 1_070_777_777;
final int BASE = (int) 8e8 + new Random().nextInt((int) 1e8); // 随机 base，防止 hack
int[] powBase = new int[n + 1]; // powBase[i] = base^i
int[] preHash = new int[n + 1]; // 前缀哈希值 preHash[i] = hash(target[0] 到 target[i-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, Integer> minCost = new HashMap<>(); // 哈希值 -> 最小成本
for (int i = 0; i < words.length; i++) {
long h = 0;
for (char b : words[i].toCharArray()) {
h = (h * BASE + b) % MOD;
}
minCost.merge((int) h, costs[i], Integer::min);
}
// 有 O(√L) 个不同的长度
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;
}
// 计算子串 target[i-sz] 到 target[i-1] 的哈希值（计算方法类似前缀和）
int subHash = (int) (((preHash[i] - (long) preHash[i - len] * powBase[len]) % MOD + MOD) % MOD);
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];
}
}
java 解法, 执行用时: 2097 ms, 内存消耗: 53.6 MB, 提交时间: 2024-07-09 10:30:58
class Solution {
public int minimumCost(String target, String[] words, int[] costs) {
char[] t = target.toCharArray();
int n = t.length;
// 多项式字符串哈希（方便计算子串哈希值）
// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
final int MOD = 1_070_777_777;
final int BASE = (int) 8e8 + new Random().nextInt((int) 1e8); // 随机 base，防止 hack
int[] powBase = new int[n + 1]; // powBase[i] = base^i
int[] preHash = new int[n + 1]; // 前缀哈希值 preHash[i] = hash(target[0] 到 target[i-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;
}
// 计算子串 target[i-sz] 到 target[i-1] 的哈希值（计算方法类似前缀和）
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];
}
}
python3 解法, 执行用时: 10973 ms, 内存消耗: 83.8 MB, 提交时间: 2024-07-09 10:30:25
# 字符串hash+dp
class Solution:
def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
n = len(target)
# 多项式字符串哈希（方便计算子串哈希值）
# 哈希函数 hash(s) = s[0] * BASE^(n-1) + s[1] * BASE^(n-2) + ... + s[n-2] * BASE + s[n-1]
MOD = 1_070_777_777
BASE = randint(8 * 10 ** 8, 9 * 10 ** 8) # 随机 BASE，防止 hack
pow_base = [1] + [0] * n # pow_base[i] = BASE^i
pre_hash = [0] * (n + 1) # 前缀哈希值 pre_hash[i] = hash(s[:i])
for i, b in enumerate(target):
pow_base[i + 1] = pow_base[i] * BASE % MOD
pre_hash[i + 1] = (pre_hash[i] * BASE + ord(b)) % MOD # 秦九韶算法计算多项式哈希
# 每个 words[i] 的哈希值 -> 最小成本
min_cost = defaultdict(lambda: inf)
for w, c in zip(words, costs):
h = 0
for b in w:
h = (h * BASE + ord(b)) % MOD
min_cost[h] = min(min_cost[h], c)
# 有 O(√L) 个不同的长度
sorted_lens = sorted(set(map(len, words)))
f = [0] + [inf] * n
for i in range(1, n + 1):
for sz in sorted_lens:
if sz > i:
break
# 计算子串 target[i-sz:i] 的哈希值（计算方法类似前缀和）
sub_hash = (pre_hash[i] - pre_hash[i - sz] * pow_base[sz]) % MOD
# 手写 min，避免超时
res = f[i - sz] + min_cost[sub_hash]
if res < f[i]:
f[i] = res
return -1 if f[n] == inf else f[n]