| comments | difficulty | edit_url | rating | source | tags | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
2081 |
第 415 场周赛 Q3 |
|
给你一个字符串数组 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 * 103- 输入确保
sum(words[i].length) <= 105。 words[i]只包含小写英文字母。1 <= target.length <= 5 * 103target只包含小写英文字母。
我们可以使用字典树存储所有有效字符串，然后使用记忆化搜索计算答案。
我们设计一个函数
函数
- 如果
$i \geq n$ ，表示字符串$\textit{target}$ 已经遍历完了，返回$0$ ； - 否则，我们可以从字典树中找到以
$\textit{target}[i]$ 开头的有效字符串，然后递归计算$\textit{dfs}(i + \text{len}(w))$ ，其中$w$ 是找到的有效字符串。我们取这些值中的最小值加$1$ 作为$\textit{dfs}(i)$ 的返回值。
为了避免重复计算，我们使用记忆化搜索。
时间复杂度
def min(a: int, b: int) -> int:
return a if a < b else b
class Trie:
def __init__(self):
self.children: List[Optional[Trie]] = [None] * 26
def insert(self, w: str):
node = self
for i in map(lambda c: ord(c) - 97, w):
if node.children[i] is None:
node.children[i] = Trie()
node = node.children[i]
class Solution:
def minValidStrings(self, words: List[str], target: str) -> int:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
node = trie
ans = inf
for j in range(i, n):
k = ord(target[j]) - 97
if node.children[k] is None:
break
node = node.children[k]
ans = min(ans, 1 + dfs(j + 1))
return ans
trie = Trie()
for w in words:
trie.insert(w)
n = len(target)
ans = dfs(0)
return ans if ans < inf else -1class Trie {
Trie[] children = new Trie[26];
void insert(String w) {
Trie node = this;
for (int i = 0; i < w.length(); ++i) {
int j = w.charAt(i) - 'a';
if (node.children[j] == null) {
node.children[j] = new Trie();
}
node = node.children[j];
}
}
}
class Solution {
private Integer[] f;
private char[] s;
private Trie trie;
private final int inf = 1 << 30;
public int minValidStrings(String[] words, String target) {
trie = new Trie();
for (String w : words) {
trie.insert(w);
}
s = target.toCharArray();
f = new Integer[s.length];
int ans = dfs(0);
return ans < inf ? ans : -1;
}
private int dfs(int i) {
if (i >= s.length) {
return 0;
}
if (f[i] != null) {
return f[i];
}
Trie node = trie;
f[i] = inf;
for (int j = i; j < s.length; ++j) {
int k = s[j] - 'a';
if (node.children[k] == null) {
break;
}
f[i] = Math.min(f[i], 1 + dfs(j + 1));
node = node.children[k];
}
return f[i];
}
}class Trie {
public:
Trie* children[26]{};
void insert(string& word) {
Trie* node = this;
for (char& c : word) {
int i = c - 'a';
if (!node->children[i]) {
node->children[i] = new Trie();
}
node = node->children[i];
}
}
};
class Solution {
public:
int minValidStrings(vector<string>& words, string target) {
int n = target.size();
Trie* trie = new Trie();
for (auto& w : words) {
trie->insert(w);
}
const int inf = 1 << 30;
int f[n];
memset(f, -1, sizeof(f));
auto dfs = [&](this auto&& dfs, int i) -> int {
if (i >= n) {
return 0;
}
if (f[i] != -1) {
return f[i];
}
f[i] = inf;
Trie* node = trie;
for (int j = i; j < n; ++j) {
int k = target[j] - 'a';
if (!node->children[k]) {
break;
}
node = node->children[k];
f[i] = min(f[i], 1 + dfs(j + 1));
}
return f[i];
};
int ans = dfs(0);
return ans < inf ? ans : -1;
}
};type Trie struct {
children [26]*Trie
}
func (t *Trie) insert(word string) {
node := t
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
}
func minValidStrings(words []string, target string) int {
n := len(target)
trie := &Trie{}
for _, w := range words {
trie.insert(w)
}
const inf int = 1 << 30
f := make([]int, n)
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != 0 {
return f[i]
}
node := trie
f[i] = inf
for j := i; j < n; j++ {
k := int(target[j] - 'a')
if node.children[k] == nil {
break
}
f[i] = min(f[i], 1+dfs(j+1))
node = node.children[k]
}
return f[i]
}
if ans := dfs(0); ans < inf {
return ans
}
return -1
}class Trie {
children: (Trie | null)[] = Array(26).fill(null);
insert(word: string): void {
let node: Trie = this;
for (const c of word) {
const i = c.charCodeAt(0) - 'a'.charCodeAt(0);
if (!node.children[i]) {
node.children[i] = new Trie();
}
node = node.children[i];
}
}
}
function minValidStrings(words: string[], target: string): number {
const n = target.length;
const trie = new Trie();
for (const w of words) {
trie.insert(w);
}
const inf = 1 << 30;
const f = Array(n).fill(0);
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i]) {
return f[i];
}
f[i] = inf;
let node: Trie | null = trie;
for (let j = i; j < n; ++j) {
const k = target[j].charCodeAt(0) - 'a'.charCodeAt(0);
if (!node?.children[k]) {
break;
}
node = node.children[k];
f[i] = Math.min(f[i], 1 + dfs(j + 1));
}
return f[i];
};
const ans = dfs(0);
return ans < inf ? ans : -1;
}