class Solution {
public:
int minValidStrings(vector<string>& words, string target) {
}
};
3292. 形成目标字符串需要的最少字符串数 II
给你一个字符串数组 words 和一个字符串 target。
如果字符串 x 是 words 中 任意 字符串的 前缀，则认为 x 是一个 有效 字符串。
现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
示例 1：
输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
输出： 3
解释：
target 字符串可以通过连接以下有效字符串形成：
words[1] 的长度为 2 的前缀，即 "aa"。words[2] 的长度为 3 的前缀，即 "bcd"。words[0] 的长度为 3 的前缀，即 "abc"。示例 2：
输入： words = ["abababab","ab"], target = "ababaababa"
输出： 2
解释：
target 字符串可以通过连接以下有效字符串形成：
words[0] 的长度为 5 的前缀，即 "ababa"。words[0] 的长度为 5 的前缀，即 "ababa"。示例 3：
输入： words = ["abcdef"], target = "xyz"
输出： -1
提示：
1 <= words.length <= 1001 <= words[i].length <= 5 * 104sum(words[i].length) <= 105.words[i] 只包含小写英文字母。1 <= target.length <= 5 * 104target 只包含小写英文字母。原站题解
golang 解法, 执行用时: 159 ms, 内存消耗: 17.8 MB, 提交时间: 2024-09-19 09:54:29
func minValidStrings(words []string, target string) (ans 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 // 秦九韶算法计算多项式哈希
}
// 计算子串 target[l:r] 的哈希值，注意这是左闭右开区间 [l,r)
// 计算方法类似前缀和
subHash := func(l, r int) int {
return ((preHash[r]-preHash[l]*powBase[r-l])%mod + mod) % mod
}
maxLen := 0
for _, w := range words {
maxLen = max(maxLen, len(w))
}
sets := make([]map[int]bool, maxLen)
for i := range sets {
sets[i] = map[int]bool{}
}
for _, w := range words {
h := 0
for j, b := range w {
h = (h*base + int(b)) % mod
sets[j][h] = true // 注意 j 从 0 开始
}
}
curR := 0 // 已建造的桥的右端点
nxtR := 0 // 下一座桥的右端点的最大值
for i := range target {
sz := sort.Search(min(n-i, maxLen), func(sz int) bool { return !sets[sz][subHash(i, i+sz+1)] })
nxtR = max(nxtR, i+sz)
if i == curR { // 到达已建造的桥的右端点
if i == nxtR { // 无论怎么造桥，都无法从 i 到 i+1
return -1
}
curR = nxtR // 建造下一座桥
ans++
}
}
return
}
java 解法, 执行用时: 150 ms, 内存消耗: 66.7 MB, 提交时间: 2024-09-19 09:54:07
class Solution {
private static final int MOD = 1_070_777_777;
public int minValidStrings(String[] words, String target) {
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 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); // 秦九韶算法计算多项式哈希
}
int maxLen = 0;
for (String w : words) {
maxLen = Math.max(maxLen, w.length());
}
Set<Integer>[] sets = new HashSet[maxLen];
Arrays.setAll(sets, i -> new HashSet<>());
for (String w : words) {
long h = 0;
for (int j = 0; j < w.length(); j++) {
h = (h * BASE + w.charAt(j)) % MOD;
sets[j].add((int) h); // 注意 j 从 0 开始
}
}
int ans = 0;
int curR = 0; // 已建造的桥的右端点
int nxtR = 0; // 下一座桥的右端点的最大值
for (int i = 0; i < n; i++) {
int sz = calcSz(i, preHash, powBase, sets);
nxtR = Math.max(nxtR, i + sz);
if (i == curR) { // 到达已建造的桥的右端点
if (i == nxtR) { // 无论怎么造桥，都无法从 i 到 i+1
return -1;
}
curR = nxtR; // 造一座桥
ans++;
}
}
return ans;
}
private int calcSz(int i, int[] preHash, int[] powBase, Set<Integer>[] sets) {
// 开区间二分，left 一定满足要求，right 一定不满足要求
int left = 0;
int right = Math.min(preHash.length - 1 - i, sets.length) + 1;
while (left + 1 < right) {
int mid = (left + right) >>> 1;
long subHash = (((long) preHash[i + mid] - (long) preHash[i] * powBase[mid]) % MOD + MOD) % MOD;
if (sets[mid - 1].contains((int) subHash)) {
left = mid;
} else {
right = mid;
}
}
return left;
}
}
cpp 解法, 执行用时: 452 ms, 内存消耗: 187.8 MB, 提交时间: 2024-09-19 09:53:55
class Solution {
public:
int minValidStrings(const vector<string>& words, const string& target) {
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;
};
int max_len = 0;
for (auto& w : words) {
max_len = max(max_len, (int) w.length());
}
vector<unordered_set<int>> sets(max_len);
for (auto& w : words) {
long long h = 0;
for (int j = 0; j < w.size(); j++) {
h = (h * BASE + w[j]) % MOD;
sets[j].insert(h); // 注意 j 从 0 开始
}
}
auto calc_sz = [&](int i) -> int {
// 开区间二分，left 一定满足要求，right 一定不满足要求
int left = 0, right = min(n - i, max_len) + 1;
while (left + 1 < right) {
int mid = (left + right) / 2;
(sets[mid - 1].contains(sub_hash(i, i + mid)) ? left : right) = mid;
}
return left;
};
int ans = 0;
int cur_r = 0; // 已建造的桥的右端点
int nxt_r = 0; // 下一座桥的右端点的最大值
for (int i = 0; i < n; i++) {
int sz = calc_sz(i);
nxt_r = max(nxt_r, i + sz);
if (i == cur_r) { // 到达已建造的桥的右端点
if (i == nxt_r) { // 无论怎么造桥，都无法从 i 到 i+1
return -1;
}
cur_r = nxt_r; // 造一座桥
ans++;
}
}
return ans;
}
};
python3 解法, 执行用时: 2372 ms, 内存消耗: 33.5 MB, 提交时间: 2024-09-19 09:52:18
class Solution:
def minValidStrings(self, words: List[str], target: str) -> 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 # 秦九韶算法计算多项式哈希
# 计算子串 target[l:r] 的哈希值，注意这是左闭右开区间 [l,r)
# 计算方法类似前缀和
def sub_hash(l: int, r: int) -> int:
return (pre_hash[r] - pre_hash[l] * pow_base[r - l]) % MOD
# 保存每个 words[i] 的每个前缀的哈希值，按照长度分组
max_len = max(map(len, words))
sets = [set() for _ in range(max_len)]
for w in words:
h = 0
for j, b in enumerate(w):
h = (h * BASE + ord(b)) % MOD
sets[j].add(h) # 注意 j 从 0 开始
ans = 0
cur_r = 0 # 已建造的桥的右端点
nxt_r = 0 # 下一座桥的右端点的最大值
for i in range(n):
check = lambda sz: sub_hash(i, i + sz + 1) not in sets[sz]
sz = bisect_left(range(min(n - i, max_len)), True, key=check)
nxt_r = max(nxt_r, i + sz)
if i == cur_r: # 到达已建造的桥的右端点
if i == nxt_r: # 无论怎么造桥，都无法从 i 到 i+1
return -1
cur_r = nxt_r # 建造下一座桥
ans += 1
return ans