数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学精确相差一位的字符串对计数
引言
字符串由字母数字字符组成，每个字符都与一个确定的位置相关联。字符的位置范围从 0 到字符串长度。在恰好一个位置上不同的字符被称为相邻字符。
在本文中，我们将开发一段代码，该代码将输入一个字符串数组，这些字符串在恰好一个位置上有所不同。让我们来看下面的例子，以便更好地理解这个主题：
示例
示例 1 − str − {“abc”, “cba”, “dbc” , “acc”}
输出 − 2
例如，在下面的例子中，可以生成两对 {“abc”,”dbc”} 和 {“abc”, “acc”}。这些字符串分别只有一个字符位置不同。
在本文中，我们将开发一个使用 map 来存储相似字符串以及模式以获取字符串对总数的代码。C++ map 使用键值对以恒定时间复杂度存储和检索数据。
语法
substr()
substr() 方法用于从起始位置到结束位置-1访问更大字符串的子字符串。所有要访问的索引都应该是连续且有序的。
参数：
st − 起始位置
end − 结束位置，用于终止子字符串的访问
算法
接受一个字符串向量 strings
最初，维护一个计数器来存储满足条件的总对数。
维护两个 map 来存储相同的字符串以及满足模式（保留通配符字符）的字符串。让我们假设这个 map 为 m1。
另一个 map 用于存储相似的字符串。让我们假设这个 map 为 m2。
对输入数组进行迭代。
每次观察到相同类型的字符串时，其对应的计数在 m2 map 中递增。
使用字符串的相应字符替换通配符字符来创建子字符串。
每次观察到相同类型的模式时，其对应的计数在 m1 map 中递增。
计算分别在 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
结论
map 模拟了在 O(1) 时间复杂度下插入和更新记录的过程。C++ 中的 substr 方法可以用于按顺序访问指定索引之间字符串的字符。直到任何数字 n 的对的总和由 n 和 n-1 的乘积除以 2 得到。
249 次浏览
