C++ 具有长度为K的共同前缀的字符串的最大数量

在这个问题中，我们需要计算具有长度为K的共同前缀的最大字符串数量。我们可以从所有字符串中获取长度为K的前缀，并使用map数据结构计算具有最大相似前缀的数量。此外，我们还可以使用Trie数据结构来解决这个问题。

问题陈述 - 我们给出一个包含多个字符串的strs []数组。我们需要计算包含长度为K的共同前缀的最大字符串数。

示例例子

输入

strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
 K = 3;

输出结果

4

解释 - 这4个字符串之中包含3个字符的’tut’前缀。

输入

strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
 K = 8;

输出

2

说明 - 只有两个字符串具有相同的长度为8的前缀，即“tutorial”。

输入

strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
 K = 8;

输出

1

说明 - 数组不包含长度为2的公共前缀字符串。所以我们可以打印1。

方法1

在这种方法中，我们将使用map数据结构来计算每个子字符串长度为K的前缀的频率。最后，我们选择频率最高的前缀在输出中显示。

算法

步骤1 - 初始化’ans’为0，用于存储具有公共前缀的最大字符串的数量。还要定义’pref’ map，用于存储字符串的前缀的频率。

步骤2 - 开始遍历字符串。

步骤3 - 取长度为K的子字符串，从0开始，并存储在’temp’字符串中。

步骤4 - 在map中将’temp’的频率增加1。

步骤5 - 从’ans’和’temp’字符串的频率中获取最大答案。

步骤6 - 最后，返回’ans’的值。

示例

#include <bits/stdc++.h>
using namespace std;

int getMaxStrs(vector<string> strs, int K) {
   int ans = 0;
   // Map to store prefix of length K
   map<string, int> pref;
   // Traverse string
   for (int p = 0; p < strs.size(); p++) {
      // Taking substring of length K
      string temp = strs[p].substr(0, K);
      // Insert the prefix into the map
      pref[temp]++;
      // Get the maximum answer
      ans = max(ans, pref[temp]);
   }
   return ans;
}
int main() {
   vector<string> strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
   int K = 3;
   cout << "The number of strings having a common prefix of length K is " << getMaxStrs(strs, K);
   return 0;
}

输出

The number of strings having a common prefix of length K is 4

时间复杂度 – O(N) 用于遍历字符串。

空间复杂度 – O(N) 用于存储映射中前缀的频率。

方法2

在这个方法中，我们将使用Trie数据结构来查找具有相同前缀的最大字符串数。我们将在Trie中插入所有字符串的前缀，并检查它是否出现了最多次数。

算法

步骤1 - 初始化trie的节点，包括指向当前节点的长度为26的字母字符数组，以及初始化为0的’cnt’变量，表示共有多少个公共前缀。

步骤2 - 开始遍历数组中的每个字符串，执行insertNode()函数将字符串的长度为K的前缀插入到Trie中。同时，将’ans’变量作为引用传递，用于存储具有公共前缀的最大字符串数。

步骤3 - 在insertNode()函数中，使用’head’节点初始化’temp’节点，并遍历字符串将其前缀插入到Trie中。

步骤4 - 使用toLower()方法将字符转换为小写。

步骤5 - 如果temp节点的’chars’数组的(ch – ‘a’)索引为空，将其赋值为新节点。

步骤6 - 增加temp->chars[ch – ‘a’]节点的’cnt’。

步骤7 - 如果p + 1等于K，表示已将长度为K的前缀插入到Trie中。因此，将’ans’更新为’ans’和temp->chars[ch – ‘a’]->cnt的最大值，并跳出循环。

步骤8 - 将temp节点移动到下一个节点。

步骤9 - 最后打印’ans’的值。

例子

#include <bits/stdc++.h>
using namespace std;

struct Node {
   Node *chars[26];
   int cnt = 0;
};
Node* head;
void insertNode(string &str, int K, int &ans) {
   // Temporary node
   Node *temp = head;
   // Traverse string characters
   for (int p = 0; p < str.size(); p++) {
      // Change character to lowercase
      char ch = tolower(str[p]);
      // If the node does not exist for the current character, initialize it
      if (temp->chars[ch - 'a'] == NULL) {
         temp->chars[ch - 'a'] = new Node();
      }
      // Increase count to increment the length of the prefix
      temp->chars[ch - 'a']->cnt++;
      // If p + 1 is equal to K, then get the maximum result and break the loop.
      if (p + 1 == K) {
         ans = max(ans, temp->chars[ch - 'a']->cnt);
         break;
      }
      // Go to the next pointer
      temp = temp->chars[ch - 'a'];
   }
}
int main() {
   vector<string> strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
   int K = 3;
   int ans = 0;
   // Node initialization
   head = new Node(); 
   // Insert all the strings into Trie
   for (auto str : strs) {
      insertNode(str, K, ans);
   }
   cout << "The number of strings having a common prefix of length K is " << ans;
   return 0;
}

输出

The number of strings having a common prefix of length K is 4

时间复杂度 – O(N*K)，其中N是数组长度，K是前缀长度。

空间复杂度 – O(N*K) 用于存储Trie中的所有字符串。

第一种方法更高效且易于初学者程序员理解。第二种方法可能更复杂，但学习Trie数据结构的概念是必要的。