Nhóm chuỗi tương tự trong C++

Hai chuỗi X, Y tương tự nếu hoán vị 2 ký tự của X được Y (hoặc X=Y). Cho danh sách A các chuỗi anagram nhau. Tìm số nhóm liên thông bởi quan hệ tương tự.

Ví dụ: ["tars","rats","arts","star"] → 2 nhóm: {tars, rats, arts} và {star}.

Giải thuật

1. Dùng Union-Find gom nhóm.
2. Hai chuỗi tương tự nếu số vị trí khác nhau ≤ 2 (và là anagram nên tự động thỏa mãn điều kiện hoán vị).
3. Duyệt mọi cặp (i,j), nếu ok(A[i], A[j]) thì union(i,j).
4. Số nhóm = số root trong DSU.

Ví dụ mã C++

#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, 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), 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, 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;
    }
};
int main(){
    Solution ob;
    vector<string> v = {"tars","rats","arts","star"};
    cout << (ob.numSimilarGroups(v));
}

Đầu vào

{"tars","rats","arts","star"}

Đầu ra

2