資料結構
網路
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 次檢視
