C++ 查询每个查询字符串的前缀数的字符串数组计数

在这个问题中，我们将计算包含查询字符串作为前缀的字符串的数量，对于每个查询字符串。

我们可以遍历查询字符串列表，对于每个查询，我们可以找到包含它作为前缀的字符串的数量。此外，我们可以使用trie数据结构来解决这个问题。

问题陈述 - 我们提供了一个包含N个字符串的字符串数组strs[]和一个包含Q个字符串的queStr[]数组。我们需要计算从strs[]数组中包含queStr[i]字符串作为前缀的字符串的数量，对于queStr[]数组中的每个字符串。

示例

输入

strs = {"tutorial", "tutorials", "tutorialspoint", "tut", "pqe"}; queStr = {"tutorials", 
"tuto", "pq"};

输出

2, 3, 1

‘教程’和’tutorialspoint’包含’tutorials’查询作为前缀。
教程’、’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

在这个方法中，我们将使用字典树数据结构来解决问题。字典树也被称为前缀树，可以用于在大型数据集中搜索字符串。

它在每个节点存储字符，根节点包含空字符串。在这里，我们将使用链表来创建字典树。此外，我们还将存储每个节点的字符和分支计数。

我们将存储每个节点的前缀计数，表示包含相同前缀的字符串数量。之后，在查找查询作为前缀时，我们可以使用查询字符串的最后一个字符的前缀计数作为答案。

算法

步骤1 - 创建名为’treeNode’的结构体，表示字典树数据结构的节点。

步骤2 - 定义’prefCnt’变量和类型为’trieNode’的数组，数组在节点内部大小为26。同时，使用构造函数将’prefCnt’初始化为0，将所有数组元素初始化为Null。

步骤3 - 定义createTrie()函数来构建字典树。

步骤3.1 - 在createTrie()函数中定义’temp’节点。

步骤3.2 - 遍历数组的每个字符串，并使用’head’将’temp’节点初始化。同时，遍历字符串的字符。

步骤3.3 - 如果在temp节点的数组索引上包含空值等于字符值，则在该索引上添加一个新节点。

步骤3.4 – 将’temp’节点的’prefCnt’递增1。

步骤3.5 - 根据字符串的当前字符更新temp节点。

步骤4 - 初始化’res’列表，用于存储包含查询作为前缀的字符串计数。

步骤5 - 执行createList()函数来初始化字典树。

步骤6 - 对于每个查询，执行findQuery()函数来获取计数并插入到’res’列表中。

步骤6.1 - 在findQuery()函数中，开始遍历字典树。

步骤6.2 - 如果在当前节点的数组索引上包含空值等于字符值，则返回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;
}