数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究针对 Q 个查询，统计数组中具有给定前缀的字符串数量
在这个问题中，我们将统计每个查询字符串中包含查询字符串作为前缀的字符串数量。
我们可以遍历查询字符串列表，并针对每个查询找到包含它作为前缀的字符串数量。此外，我们还可以使用 Trie 数据结构来解决此问题。
问题陈述 – 我们给定了一个 strs[] 和 queStr[] 字符串数组，分别包含 N 和 Q 个字符串。我们需要统计 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[] 查询数组，并在每次迭代中将 “cnt” 初始化为 0。
步骤 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) {
// To store count of string containing x as prefix
int cnt = 0;
for (string str : strs) {
// For query's greater length than string
if (str.size() < que.size()) {
continue;
}
// For string containing query as prefix
if (str.substr(0, que.size()) == que) {
cnt++;
}
}
// Insert count to vector
counts.push_back(cnt);
}
return counts;
}
int main() {
// List of strings and Queries
vector<string> strs = {"tutorial", "tutorials", "tutorialspoint", "tut", "pqe"};
vector<string> queStr = {"tutorials", "tuto", "pq"};
vector<int> counts = findPrefixCounts(strs, queStr);
// Printing the counts
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 - 创建一个名为 “treeNode” 的结构体，表示 Trie 数据结构的节点。
步骤 2 - 在节点内部定义 “prefCnt” 变量和类型为 “trieNode” 的数组，该数组的大小等于 26。此外，使用构造函数将 “prefCnt” 初始化为 0，并将所有数组元素初始化为 Null。
步骤 3 - 定义 createTrie() 函数来构建 Trie。
步骤 3.1 - 在 createTrie() 函数中定义 “temp” 节点。
步骤 3.2 - 遍历数组的每个字符串，并将 “temp” 节点初始化为 “head”。此外，遍历字符串字符。
步骤 3.3 - 在 temp 节点中，如果数组在等于字符值的索引处包含 null，则在该索引处添加一个新节点。
步骤 3.4 - 将 “temp” 节点的 “prefCnt” 加 1。
步骤 3.5 - 根据字符串的当前字符更新 temp 节点。
步骤 4 - 初始化 “res” 列表以存储包含查询作为前缀的字符串计数。
步骤 5 - 执行 createList() 函数以初始化 Trie。
步骤 6 - 对于每个查询，执行 findQuery() 函数以获取计数并将其插入 “res” 列表。
步骤 6.1 - 在 findQuery() 函数中，开始遍历 Trie。
步骤 6.2 - 如果数组在当前节点中等于字符值的索引处包含 null，则返回 0。
步骤 6.3 - 根据当前字符串字符更新 head。
步骤 6.4 - 返回 head 节点的 “prefCnt” 值。
示例
#include <bits/stdc++.h>
using namespace std;
int len;
// Trie node
struct trieNode {
// To store the count of a string with the current prefix
int prefCnt;
trieNode *ch[26];
// Constructor
trieNode() {
prefCnt = 0;
for (int p = 0; p < 26; p++)
ch[p] = NULL;
}
};
void createTrie(vector<string> &list, trieNode *head) {
// Creating the temporary node
trieNode *temp;
for (int p = 0; p < len; p++) {
temp = head;
// Inserting the string in 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();
// Create a trie
createTrie(list, head);
// Finding the count of a string with the current prefix value
for (int p = 0; p < que_len; p++) {
res.push_back(findQuery(query[p], head));
}
return res;
}
// Driver Code
int main() {
// List of strings and Queries
vector<string> strs = {"tutorial", "tutorials", "tutorialspoint", "tut",
"pqe"};
vector<string> queStr = {"tutorials", "tuto", "pq"};
vector<int> counts = findPrefixCounts(strs.size(), queStr.size(), strs,
queStr);
// Printing the counts
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 数据结构。
193 次查看
