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 只包含小写英文字母。原站题解
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]