首页 > 后端开发 > C++ > 正文

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

WBOY
发布: 2023-09-04 20:13:05
转载
759人浏览过

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

简介

字符串由字母数字字符组成,每个字符都与一个确定的位置相关联。字符的位置范围从 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中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
相关标签:
来源:tutorialspoint网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号