3291. Minimum Number of Valid Strings to Form Target I
You are given an array of strings words and a string target.
A string x is called valid if x is a prefix of any string in words.
Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.
A prefix of a string is a substring that starts from the beginning of the string and extends to any point within it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| long long mem[50505];
struct Trie{
Trie* next[26];
Trie() {
memset(next, 0, sizeof next);
}
void insert(string& s, int p = 0) {
if(p == s.length()) return;
if(!next[s[p]-'a']) next[s[p]-'a'] = new Trie();
next[s[p]-'a']->insert(s,p+1);
}
void query(string& s, int p, long long c) {
if(p == s.length()) return;
if(!next[s[p]-'a']) return;
mem[p+1] = min(mem[p+1], c + 1);
next[s[p]-'a']->query(s,p+1,c);
}
};
class Solution {
public:
int minValidStrings(vector<string>& words, string target) {
memset(mem, -1, sizeof mem);
mem[0] = 0;
Trie* t = new Trie();
for(auto& w : words) t->insert(w);
for(int i = 1; i <= target.length(); i++) mem[i] = INT_MAX;
for(int i = 0; i < target.length(); i++) {
if(mem[i] == INT_MAX) continue;
t->query(target,i,mem[i]);
}
return mem[target.length()] == INT_MAX ? -1 : mem[target.length()];
}
};
|
