C ++中的相似字符串组
假设我们有两个字符串X和Y，如果可以交换X的两个字母，它们是相似的，因此等于Y。另外，如果两个字符串X和Y相等，则它们相似。例如，考虑两个字符串，例如“tars”和“rats”相似，如果我们交换t和r，则可以找到另一个，现在“rats”和“arts”相似，但是“star”不同类似于“焦油”，“鼠”或“艺术品”。现在我们可以看到，它们通过相似性形成了两个相连的组：{“tars”，“rats”，“arts”}和{“star”}。尽管“焦油”和“艺术品”不相似，但它们属于同一组。因此，当且仅当单词与该组中的至少一个其他单词相似时，每个组才使得该单词在该组中。假设我们有一个字符串列表A。A中的每个字符串都是A中其他所有字符串的相似词。我们必须找出那里有多少个组？
因此，如果输入类似于[“tars”，“rats”，“arts”，“star”]，则输出将为2
为了解决这个问题，我们将遵循以下步骤-
定义一个父数组
定义数组等级
定义一个函数getParent()，这将需要x，
返回x
如果parent[x]与-1相同，则-
返回parent[x]=getParent（parent[x]）
定义一个函数unionn()，它将取x，y，
等级[parY]：=等级[parY]+等级[parX]
parent[parX]：=parY
等级[parX]：=等级[parX]+等级[parY]
parent[parY]：=parX
返回假
parX：=getParent(x)，parY：=getParent(y)
如果parX与parY相同，则-
如果rank[parX]>=rank[parY]，则-
除此以外
返回真
定义一个函数ok()，它将取s1，s2，
如果s1[i]不等于s2[i]，则-
如果cnt>2，则-
（将cnt增加1）
返回假
cnt：=0
对于初始化i：=0，当i<s1的大小时，更新（将i增加1），执行-
返回真
从主要方法中，执行以下操作-
ret：=0
n：=A的大小
ret：=n
parent：=一个大小为n的数组，并用-1填充
rank：=大小为n的数组，并用1填充
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
如果ok（A[i]，A[j]）不为零，则-
（将retret减少1）
如果unionn(i,j)不为零，则-
对于初始化j：=i+1，当j<n时，更新（将j增加1），-
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> parent;
vector<int> rank;
int getParent(int x){
if (parent[x] == -1)
return x;
return parent[x] = getParent(parent[x]);
}
bool unionn(int x, int y){
int parX = getParent(x);
int parY = getParent(y);
if (parX == parY)
return false;
if (rank[parX] >= rank[parY]) {
rank[parX] += rank[parY];
parent[parY] = parX;
} else {
rank[parY] += rank[parX];
parent[parX] = parY;
}
return true;
}
bool ok(string& s1, string& s2){
int cnt = 0;
for (int i = 0; i < s1.size(); i++) {
if (s1[i] != s2[i])
cnt++;
if (cnt > 2)
return false;
}
return true;
}
int numSimilarGroups(vector<string>& A){
int ret = 0;
int n = A.size();
ret = n;
parent = vector<int>(n, -1);
rank = vector<int>(n, 1);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (ok(A[i], A[j])) {
if (unionn(i, j))
ret--;
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"tars","rats","arts","star"};
cout << (ob.numSimilarGroups(v));
}输入值
{"tars","rats","arts","star"}输出结果
2