数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的相似字符串组
假设我们有两个字符串 X 和 Y，如果我们可以交换 X 的两个字母，使其等于 Y，则它们是相似的。如果两个字符串 X 和 Y 相等，则它们也是相似的。例如，考虑两个字符串“tars”和“rats”是相似的，如果我们交换 t 和 r，那么我们可以找到另一个，现在“rats”和“arts”是相似的，但“star”与“tars”、“rats”或“arts”都不相似。现在我们可以看到，这些通过相似性形成了两个连接的组：{"tars", "rats", "arts"} 和 {"star"}。这里“tars”和“arts”在同一组中，即使它们不相似。因此，每个组都是这样的，即一个单词在一个组中当且仅当它与该组中的至少一个其他单词相似。假设我们有一个字符串列表 A。A 中的每个字符串都是 A 中每个其他字符串的字谜。我们必须找到有多少个组？
因此，如果输入类似于 ["tars","rats","arts","star"]，则输出将为 2
要解决此问题，我们将遵循以下步骤：
定义一个数组 parent
定义一个数组 rank
定义一个函数 getParent()，它将接收 x，
如果 parent[x] 与 -1 相同，则：
返回 x
返回 parent[x] = getParent(parent[x])
定义一个函数 unionn()，它将接收 x、y，
parX := getParent(x), parY := getParent(y)
如果 parX 与 parY 相同，则：
返回 false
如果 rank[parX] >= rank[parY]，则：
rank[parX] := rank[parX] + rank[parY]
parent[parY] := parX
否则
rank[parY] := rank[parY] + rank[parX]
parent[parX] := parY
返回 true
定义一个函数 ok()，它将接收 s1、s2，
cnt := 0
对于初始化 i := 0，当 i < s1 的大小，更新（i 增加 1），执行：
如果 s1[i] 不等于 s2[i]，则：
（cnt 增加 1）
如果 cnt > 2，则：
返回 false
返回 true
从主方法中，执行以下操作：
ret := 0
n := A 的大小
ret := n
parent := 一个大小为 n 的数组，并用 -1 填充它
rank := 一个大小为 n 的数组，并用 1 填充它
对于初始化 i := 0，当 i < n，更新（i 增加 1），执行：
对于初始化 j := i + 1，当 j < n，更新（j 增加 1），执行：
如果 ok(A[i], A[j]) 不为零，则：
如果 unionn(i, j) 不为零，则：
（ret 减 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
205 次查看
