C++ 字符串对的计数，仅在一个位置上有所不同

介绍

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

在本文中，我们将开发一个代码，该代码以一个只在一个位置上不同的字符串数组作为输入。让我们来看一下以下示例，以更好地理解该主题−

示例

示例1−str−{“abc”，“cba”，“dbc”，“acc”}

输出−2

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

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

语法

substr()

substr()方法用于访问大字符串的子字符串，从开始位置到结束-1位置。要访问的所有索引应该是连续的且按顺序排列。

参数 −

st−起始位置

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

步骤

• 接受一个字符串向量strings。

• 初始情况下，保持一个计数器以存储满足条件的总对数。

• 维护两个映射以存储相同的字符串以及满足模式的字符串，保持通配符字符。让我们假设这个映射为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

结论

地图在O（1）时间复杂度内模拟插入和更新记录的过程。C++中的子字符串方法可以用于在特定索引之间按顺序访问字符串的字符。任意数字n之前的成对求和可以通过n乘以n-1再除以2得到。