计算在仅一个位置上不同的字符串对的数量

简介

字符串由字母数字字符组成，每个字符都与一个确定的位置相关联。字符的位置范围从 0 到字符串长度。在一个位置完全不同的字符称为相邻字符。

在本文中，我们将开发一种代码，该代码将一个字符串数组作为输入，这些字符串在一个位置上完全不同。让我们看下面的例子来更好地理解这个主题 -

示例

示例 1 - str - {“abc”、“cba”、“dbc”、“acc”}

输出 - 2

例如，在下面的示例中，可以生成两对{“abc”，“dbc”}和{“abc”，acc”}。这些字符串分别仅在一个字符位置上有所不同。

在本文中，我们将开发一个代码，利用映射来存储相似的字符串以及获取字符串对总数的模式。 C++ 映射利用键值对以便以恒定的时间复杂度存储和检索数据。

语法

substr()

substr() 方法用于访问较大字符串中从 start 到 end-1 位置的子字符串。所有要访问的索引应该是连续且有序的。

参数 -

st - 起始位置

end - 终止子字符串访问的结束位置

算法

• 接受字符串向量，字符串

• 最初维护一个计数器来存储满足条件的总对的计数。

• 维护两个映射来存储相同的字符串以及满足保留通配符的模式的字符串。让我们假设这个映射是 m1。

• 维护另一个映射来存储相似的字符串。让我们假设这个映射是 m2。

• 对输入数组执行迭代。

• 每次观察到相似类型的字符串，m2 映射中其对应的计数就会递增

• 子字符串是通过使用通配符替换字符串的各个字符来创建的

• 每次观察到相似类型的模式，m1 图中相应的计数就会增加

• 计算分别在 m1 和 m2 中观察到的字符串对的总和。

• 使用这些总和值来增加计数。

示例

以下 C++ 代码片段用于将字符串数组作为输入，并计算仅在一个位置不同的对的总数 -

//including the required libraries
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of same pairs
int countPairs(map<string, int> &d) {
   //maintaining the count 
   int sum = 0;
   for (auto i : d)
       sum += (i.second * (i.second - 1)) / 2;
 
   return sum;
}
//called method to calculate strings differing by one character
void chardiff(vector<string> &array, int len , int n ) {
   //count to store pairs
    int cnt = 0;
   //storing strings with wildcard characters
    map<string, int> pattern;
   //storing equivalent strings
    map<string, int> similar;
   //iterating over the array
   for (auto str : array) {
      //if two strings are same , increment the count
       similar[str]+= 1;
 
      // Iterating on a single string
       for (int i = 0; i < len ; i++) {
      // Adding special symbol to the string
       string first = str.substr(0, i);
       string second = str.substr(i + 1);
       string temp =  first + "//" + second ;
 
      //incrementing if similar pattern 
        pattern[temp]+=1;
      }
   }
 
   // Return counted pairs - equal pairs
   int chnged = countPairs(pattern);
   int sim = countPairs(similar);
   cnt =  chnged - sim * len;
   cout << "The count of pairs satisfying the condition are : " << cnt; 
}
 
//calling the main method
int main() {
   int n = 4, len = 3;
   //getting a vector of strings to process
   vector<string> strings = {"get","set","bet","bat"};
   cout << "Vector of strings : " << "\n" ;
   for(auto s : strings){
       cout << s <<"\n";
   }
   //one character different
   chardiff(strings, len , n );
 
   return 0;
}

输出

Vector of strings − 
get
set
bet
bat
The count of pairs satisfying the condition are − 4

结论

Maps 以 O(1) 时间复杂度模拟记录插入和更新的过程。 C++ 中的 substring 方法可用于按指定索引之间的顺序访问字符串的字符。 n 和 n-1 的乘积除以 2 即可得到任意数量的对的总和。

以上是计算在仅一个位置上不同的字符串对的数量的详细内容。更多信息请关注PHP中文网其他相关文章！