class Solution {
public:
int minValidStrings(vector<string>& words, string target) {
}
};
3291. 形成目标字符串需要的最少字符串数 I
给你一个字符串数组 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 * 103sum(words[i].length) <= 105。words[i] 只包含小写英文字母。1 <= target.length <= 5 * 103target 只包含小写英文字母。原站题解
javascript 解法, 执行用时: 154 ms, 内存消耗: 59.2 MB, 提交时间: 2024-12-17 07:43:01
/**
* @param {string[]} words
* @param {string} target
* @return {number}
*/
var minValidStrings = function(words, target) {
const prefixFunction = (word, target) => {
const s = word + '#' + target;
const n = s.length;
const pi = new Array(n).fill(0);
for (let i = 1; i < n; i++) {
let j = pi[i - 1];
while (j > 0 && s[i] !== s[j]) {
j = pi[j - 1];
}
if (s[i] === s[j]) {
j++;
}
pi[i] = j;
}
return pi;
};
const n = target.length;
const back = new Array(n).fill(0);
for (const word of words) {
const pi = prefixFunction(word, target);
const m = word.length;
for (let i = 0; i < n; i++) {
back[i] = Math.max(back[i], pi[m + 1 + i]);
}
}
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
dp[i] = 1e9;
}
for (let i = 0; i < n; i++) {
dp[i + 1] = dp[i + 1 - back[i]] + 1;
if (dp[i + 1] > n) {
return -1;
}
}
return dp[n];
};
rust 解法, 执行用时: 27 ms, 内存消耗: 2.8 MB, 提交时间: 2024-12-17 07:42:45
pub fn prefix_function(word: &str, target: &str) -> Vec<usize> {
let s = word.to_owned() + "#" + target;
let n = s.len();
let mut pi = vec![0; n];
for i in 1..n {
let mut j = pi[i - 1];
while j > 0 && s.as_bytes()[i] != s.as_bytes()[j] {
j = pi[j - 1];
}
if s.as_bytes()[i] == s.as_bytes()[j] {
j += 1;
}
pi[i] = j;
}
pi
}
impl Solution {
pub fn min_valid_strings(words: Vec<String>, target: String) -> i32 {
let n = target.len();
let mut back = vec![0; n];
for word in words {
let pi = prefix_function(&word, &target);
let m = word.len();
for i in 0..n {
back[i] = std::cmp::max(back[i], pi[m + 1 + i]);
}
}
let mut dp = vec![0; n + 1];
for i in 1..=n {
dp[i] = 1_000_000_000;
}
for i in 0..n {
dp[i + 1] = dp[i + 1 - back[i]] + 1;
if dp[i + 1] > n as i32 {
return -1;
}
}
dp[n] as i32
}
}
golang 解法, 执行用时: 53 ms, 内存消耗: 11.1 MB, 提交时间: 2024-12-17 07:42:23
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 {
maxJump := sort.Search(min(n-i, maxLen), func(j int) bool { return !sets[j][subHash(i, i+j+1)] })
nxtR = max(nxtR, i+maxJump)
if i == curR { // 到达已建造的桥的右端点
if i == nxtR { // 无论怎么造桥，都无法从 i 到 i+1
return -1
}
curR = nxtR // 建造下一座桥
ans++
}
}
return
}
python3 解法, 执行用时: 550 ms, 内存消耗: 26 MB, 提交时间: 2024-12-17 07:42:09
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 j: sub_hash(i, i + j + 1) not in sets[j]
max_jump = bisect_left(range(min(n - i, max_len)), True, key=check)
nxt_r = max(nxt_r, i + max_jump)
if i == cur_r: # 到达已建造的桥的右端点
if i == nxt_r: # 无论怎么造桥，都无法从 i 到 i+1
return -1
cur_r = nxt_r # 建造下一座桥
ans += 1
return ans
golang 解法, 执行用时: 156 ms, 内存消耗: 27.9 MB, 提交时间: 2024-09-19 09:53:32
// 从根到 node 的字符串是某个（某些）words[i] 的前缀
type node struct {
son [26]*node
fail *node // 当 cur.son[i] 不能匹配 target 中的某个字符时，cur.fail.son[i] 即为下一个待匹配节点（等于 root 则表示没有匹配）
len int // 从根到 node 的字符串的长度，也是 node 在 trie 中的深度
}
type acam struct {
root *node
}
func (ac *acam) put(s string) {
cur := ac.root
for _, b := range s {
b -= 'a'
if cur.son[b] == nil {
cur.son[b] = &node{len: cur.len + 1}
}
cur = cur.son[b]
}
}
func (ac *acam) buildFail() {
ac.root.fail = ac.root
q := []*node{}
for i, son := range ac.root.son[:] {
if son == nil {
ac.root.son[i] = ac.root
} else {
son.fail = ac.root // 第一层的失配指针，都指向根节点 ∅
q = append(q, son)
}
}
// BFS
for len(q) > 0 {
cur := q[0]
q = q[1:]
for i, son := range cur.son[:] {
if son == nil {
// 虚拟子节点 cur.son[i]，和 cur.fail.son[i] 是同一个
// 方便失配时直接跳到下一个可能匹配的位置（但不一定是某个 words[k] 的最后一个字母）
cur.son[i] = cur.fail.son[i]
continue
}
son.fail = cur.fail.son[i] // 计算失配位置
q = append(q, son)
}
}
}
func minValidStrings(words []string, target string) int {
ac := &acam{root: &node{}}
for _, w := range words {
ac.put(w)
}
ac.buildFail()
n := len(target)
f := make([]int, n+1)
cur := ac.root
for i, b := range target {
// 如果没有匹配相当于移动到 fail 的 son[b-'a']
cur = cur.son[b-'a']
// 没有任何字符串的前缀与 target[:i+1] 的后缀匹配
if cur == ac.root {
return -1
}
f[i+1] = f[i+1-cur.len] + 1
}
return f[n]
}
java 解法, 执行用时: 70 ms, 内存消耗: 55.5 MB, 提交时间: 2024-09-19 09:53:17
// 从根到 node 的字符串是某个（某些）words[i] 的前缀
class Node {
Node[] son = new Node[26];
Node fail; // 当 cur.son[i] 不能匹配 target 中的某个字符时，cur.fail.son[i] 即为下一个待匹配节点（等于 root 则表示没有匹配）
int len;
Node(int len) {
this.len = len;
}
}
class AhoCorasick {
Node root = new Node(0);
void put(String s) {
Node cur = root;
for (char b : s.toCharArray()) {
b -= 'a';
if (cur.son[b] == null) {
cur.son[b] = new Node(cur.len + 1);
}
cur = cur.son[b];
}
}
void buildFail() {
root.fail = root;
Queue<Node> q = new ArrayDeque<>();
for (int i = 0; i < root.son.length; i++) {
Node son = root.son[i];
if (son == null) {
root.son[i] = root;
} else {
son.fail = root; // 第一层的失配指针，都指向根节点 ∅
q.add(son);
}
}
// BFS
while (!q.isEmpty()) {
Node cur = q.poll();
for (int i = 0; i < 26; i++) {
Node son = cur.son[i];
if (son == null) {
// 虚拟子节点 cur.son[i]，和 cur.fail.son[i] 是同一个
// 方便失配时直接跳到下一个可能匹配的位置（但不一定是某个 words[k] 的最后一个字母）
cur.son[i] = cur.fail.son[i];
continue;
}
son.fail = cur.fail.son[i]; // 计算失配位置
q.add(son);
}
}
}
}
class Solution {
public int minValidStrings(String[] words, String target) {
AhoCorasick ac = new AhoCorasick();
for (String w : words) {
ac.put(w);
}
ac.buildFail();
char[] t = target.toCharArray();
int n = t.length;
int[] f = new int[n + 1];
Node cur = ac.root;
for (int i = 0; i < n; i++) {
// 如果没有匹配相当于移动到 fail 的 son[t[i]-'a']
cur = cur.son[t[i] - 'a'];
// 没有任何字符串的前缀与 target[..i] 的后缀匹配
if (cur == ac.root) {
return -1;
}
f[i + 1] = f[i + 1 - cur.len] + 1;
}
return f[n];
}
}
cpp 解法, 执行用时: 213 ms, 内存消耗: 234.5 MB, 提交时间: 2024-09-19 09:53:04
// 从根到 node 的字符串是某个（某些）words[i] 的前缀
struct Node {
Node* son[26]{};
Node* fail; // 当 cur.son[i] 不能匹配 target 中的某个字符时，cur.fail.son[i] 即为下一个待匹配节点（等于 root 则表示没有匹配）
int len; // 从根到 node 的字符串的长度，也是 node 在 trie 中的深度
Node(int len) : len(len) {}
};
struct AhoCorasick {
Node* root = new Node(0);
void put(string& s) {
auto cur = root;
for (char b : s) {
b -= 'a';
if (cur->son[b] == nullptr) {
cur->son[b] = new Node(cur->len + 1);
}
cur = cur->son[b];
}
}
void build_fail() {
root->fail = root;
queue<Node*> q;
for (auto& son : root->son) {
if (son == nullptr) {
son = root;
} else {
son->fail = root; // 第一层的失配指针，都指向根节点 ∅
q.push(son);
}
}
// BFS
while (!q.empty()) {
auto cur = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
auto& son = cur->son[i];
if (son == nullptr) {
// 虚拟子节点 cur.son[i]，和 cur.fail.son[i] 是同一个
// 方便失配时直接跳到下一个可能匹配的位置（但不一定是某个 words[k] 的最后一个字母）
son = cur->fail->son[i];
continue;
}
son->fail = cur->fail->son[i]; // 计算失配位置
q.push(son);
}
}
}
};
class Solution {
public:
int minValidStrings(vector<string>& words, string target) {
AhoCorasick ac;
for (auto& w : words) {
ac.put(w);
}
ac.build_fail();
int n = target.length();
vector<int> f(n + 1);
auto cur = ac.root;
for (int i = 0; i < n; i++) {
// 如果没有匹配相当于移动到 fail 的 son[target[i]-'a']
cur = cur->son[target[i] - 'a'];
// 没有任何字符串的前缀与 target[..i] 的后缀匹配
if (cur == ac.root) {
return -1;
}
f[i + 1] = f[i + 1 - cur->len] + 1;
}
return f[n];
}
};
python3 解法, 执行用时: 1117 ms, 内存消耗: 44.5 MB, 提交时间: 2024-09-19 09:52:34
# 从根到 node 的字符串是某个（某些）words[i] 的前缀
class Node:
__slots__ = 'son', 'fail', 'len'
def __init__(self, len=0):
self.son = [None] * 26
self.fail = None # 当 cur.son[i] 不能匹配 target 中的某个字符时，cur.fail.son[i] 即为下一个待匹配节点（等于 root 则表示没有匹配）
self.len = len # 从根到 node 的字符串的长度，也是 node 在 trie 中的深度
class AhoCorasick:
def __init__(self):
self.root = Node()
def put(self, s: str) -> None:
cur = self.root
for b in s:
b = ord(b) - ord('a')
if cur.son[b] is None:
cur.son[b] = Node(cur.len + 1)
cur = cur.son[b]
def build_fail(self) -> None:
self.root.fail = self.root
q = deque()
for i, son in enumerate(self.root.son):
if son is None:
self.root.son[i] = self.root
else:
son.fail = self.root # 第一层的失配指针，都指向根节点 ∅
q.append(son)
# BFS
while q:
cur = q.popleft()
for i, son in enumerate(cur.son):
if son is None:
# 虚拟子节点 cur.son[i]，和 cur.fail.son[i] 是同一个
# 方便失配时直接跳到下一个可能匹配的位置（但不一定是某个 words[k] 的最后一个字母）
cur.son[i] = cur.fail.son[i]
continue
son.fail = cur.fail.son[i] # 计算失配位置
q.append(son)
class Solution:
def minValidStrings(self, words: List[str], target: str) -> int:
ac = AhoCorasick()
for w in words:
ac.put(w)
ac.build_fail()
n = len(target)
f = [0] * (n + 1)
cur = root = ac.root
for i, c in enumerate(target, 1):
# 如果没有匹配相当于移动到 fail 的 son[c]
cur = cur.son[ord(c) - ord('a')]
# 没有任何字符串的前缀与 target[..i] 的后缀匹配
if cur is root:
return -1
f[i] = f[i - cur.len] + 1
return f[n]