计算 Q 查询中具有给定前缀的数组字符串的数量
在此问题中，我们将计算每个查询字符串中包含查询字符串作为前缀的字符串的数量。
我们可以遍历查询字符串列表，对于每个查询，我们可以找到包含它作为前缀的字符串数量。此外，我们可以使用 trie 数据结构来解决问题。
问题陈述 – 我们给出了一个包含 N 和 Q 个字符串的 strs[] 和 queStr[] 字符串数组。我们需要从 Strs[] 数组中计算包含 queStr[i] 字符串作为 queStr[] 数组每个字符串前缀的字符串数量。
示例
输入
strs = {"tutorial", "tutorials", "tutorialspoint", "tut", "pqe"}; queStr = {"tutorials",
"tuto", "pq"};
输出
2, 3, 1
'tutorials' 和 'tutorialspoint' 包含 'tutorials' 查询作为前缀。
tutorial '、'tutorials' 和 'tutorialspoint' 包含 'tuto' 查询字符串作为前缀。
唯一的 'pqe' 字符串包含 'pq' 字符串作为前缀。
输入
strs = {"abcd", "abe", "abp", "rew", "wel"}; queStr = {"ab", "abn", "mo"};
输出
3, 0, 0
解释
'abcd'、'abe' 和 'abp' 字符串包含 'ab' 作为前缀。
任何字符串不包含 'abn' 和 'mo' 作为前缀。
输入
strs = {"aaa", "aaa", "aaa"}; queStr = {"a", "aa", "aaa"};
输出
3, 3, 3
说明 - 所有字符串都包含所有查询作为前缀。
方法 1
在此方法中，我们将遍历查询数组。我们可以遍历每个查询的字符串数组，并计算包含查询作为前缀的字符串。要检查字符串是否包含查询作为前缀，我们可以从子字符串中取出等于查询长度的子字符串并将其与查询进行匹配。
算法
步骤 1 - 创建一个名为"counts"的列表。
步骤 2 - 开始遍历查询的 queStr[] 数组，并在每次迭代中用 0 初始化"cnt"。
步骤 3 - 开始遍历 strs[] 数组，如果字符串大小小于查询大小，则转到下一次迭代。
步骤 4 - 使用 substr() 方法从第 0 个索引获取子字符串，其长度等于查询的长度。如果子字符串等于查询，则将"cnt"值增加 1。
步骤 5- 将"cnt"值插入"counts"列表。
步骤 6 - 返回"counts"列表。
示例
#include <bits/stdc++.h>
using namespace std;
vector<int> findPrefixCounts(vector<string> &strs, vector<string> &queStr) {
vector<int> counts;
for (string que : queStr) {
// 存储包含 x 作为前缀的字符串的计数
int cnt = 0;
for (string str : strs) {
// 对于查询的长度大于字符串
if (str.size() < que.size()) {
continue;
}
// 对于包含查询作为前缀的字符串
if (str.substr(0, que.size()) == que) {
cnt++;
}
}
// 将计数插入向量
counts.push_back(cnt);
}
return counts;
}
int main() {
// 字符串和查询列表
vector<string> strs = {"tutorial", "tutorials", "tutorialspoint", "tut", "pqe"};
vector<string> queStr = {"tutorials", "tuto", "pq"};
vector<int> counts = findPrefixCounts(strs, queStr);
// 打印计数
for (int cnt : counts) {
cout << cnt << ", ";
}
return 0;
}
输出
2, 3, 1,
时间复杂度 - O(N*Q*S)，其中 N 是字符串数组的长度，Q 是查询数组的长度，S 是获取子字符串的最大字符串长度。
空间复杂度 - O(Q) 用于存储每个查询的计数。
方法 2
我们将使用 trie 数据结构来解决此方法中的问题。trie 称为前缀树，我们可以使用它在大型数据集中搜索字符串。
它在每个节点存储字符，根节点包含空字符串。在这里，我们将使用链表来创建 trie。此外，我们将存储每个节点的字符和分支数。
我们将前缀计数存储到每个节点，表示包含相同前缀的字符串的数量。之后，在查找查询作为前缀时，我们可以使用查询字符串最后一个字符的前缀计数作为答案。
算法
步骤 1 - 创建一个名为 struct 的"treeNode"，表示 Trie 数据结构的节点。
步骤 2 - 定义"prefCnt"变量和"trieNode"类型的数组，其大小等于节点内部的 26。另外，使用构造函数将"prefCnt"初始化为 0，将所有数组元素初始化为 Null。
步骤 3 - 定义 createTrie() 函数来构建 trie。
步骤 3.1 - 在 createTrie() 函数中定义"temp"节点。
步骤 3.2 - 遍历数组的每个字符串，并使用"head"初始化"temp"节点。另外，遍历字符串字符。
步骤 3.3- 在临时节点中，如果数组在等于字符值的索引处包含 null，则向索引添加一个新节点。
步骤 3.4 - 将"temp"节点的"prefCnt"增加 1。
步骤 3.5 - 根据字符串的当前字符更新临时节点。
步骤 4 - 初始化"res"列表以存储包含查询作为前缀的字符串的数量。
步骤 5 - 执行 createList() 函数初始化 Trie。
步骤 6 - 对于每个查询，执行 findQuery() 函数以获取计数并插入到"res"列表中。
步骤6.1 - 在 findQuery() 函数中，开始遍历 Trie。
步骤 6.2 - 如果数组在当前节点中等于字符值的索引处包含 null，则返回 0。
步骤 6.3 - 根据当前字符串字符更新头。
步骤 6.4 - 返回头节点的"prefCnt"的值。
示例
#include <bits/stdc++.h>
using namespace std;
int len;
// Trie 节点
struct trieNode {
// 存储具有当前前缀的字符串的计数
int prefCnt;
trieNode *ch[26];
// 构造函数
trieNode() {
prefCnt = 0;
for (int p = 0; p < 26; p++)
ch[p] = NULL;
}
};
void createTrie(vector<string> &list, trieNode *head) {
// 创建临时节点
trieNode *temp;
for (int p = 0; p < len; p++) {
temp = head;
// 将字符串插入到 trieNode 中
for (int q = 0; q < list[p].size(); q++) {
if (temp->ch[list[p][q] - 'a'] == NULL)
temp->ch[list[p][q] - 'a'] = new trieNode();
temp->ch[list[p][q] - 'a']->prefCnt += 1;
temp = temp->ch[list[p][q] - 'a'];
}
}
}
int findQuery(string str, trieNode *head) {
for (int p = 0; p < str.size(); p++) {
if (head->ch[str[p] - 'a'] == NULL)
return 0;
head = head->ch[str[p] - 'a'];
}
return head->prefCnt;
}
vector<int> findPrefixCounts(int strs_len, int que_len,
vector<string> &list, vector<string> &query) {
vector<int> res;
len = strs_len;
trieNode *head = new trieNode();
// 创建一个 trie
createTrie(list, head);
// 查找具有当前前缀值的字符串的计数
for (int p = 0; p < que_len; p++) {
res.push_back(findQuery(query[p], head));
}
return res;
}
// 驱动程序代码
int main() {
// 字符串和查询列表
vector<string> strs = {"tutorial", "tutorials", "tutorialspoint", "tut",
"pqe"};
vector<string> queStr = {"tutorials", "tuto", "pq"};
vector<int> counts = findPrefixCounts(strs.size(), queStr.size(), strs,
queStr);
// 打印计数
for (int cnt : counts) {
cout << cnt << ", ";
}
return 0;
}
输出
2, 3, 1,
时间复杂度 - (Q*p + N*R)，其中 Q 是总查询数，N 是总字符串数，p 是最长查询的长度，R 是要插入 Trie 中的最长字符串的长度。
空间复杂度 - O(Q + N*26)，用于存储等于查询数的计数并创建每个节点包含大小等于 26 的数组的 trie。
我们已经使用 Trie 数据结构有效地解决了这个问题。每当我们需要根据字符串前缀获取输出时，我们都可以使用 Trie 数据结构。
