839. 相似字串組

思路

給定一系列單字，每個單字的長度相同，且包含的字元跟字元數也都相同。
如果兩個字串 $s1$ 可以通過交換一個位置的字元來得到 $s2$ ，就說這兩個字串相似。
一個相似字串組當中，其中個一個元素，需要跟相似字串組當中的任意一元素相似（自己不算），舉例來說： $\{s1,s2,s3\}$ 中， $s1$ 可以跟 $s3$ 不相似，但一定要跟集合當中的一個字串相似。
最後回傳一共有多少相似字串組。

這就很明顯是用並查集了，假如兩個字串相似，就合併到相同集合當中，最後給出集合的數量。
因為兩個字串的長度相同，構成也相同，如果兩字串有所不同，個數一定會是 0, 2, 4, …，因此能利用這個性質去判斷，將複雜度限制在 $O(n)$

程式碼

並查集

class Solution {
private:
    static const int MX = 301;
    int parent[MX];
    int setCnt = 0;
    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY) {
            parent[rootX] = rootY;
            setCnt--;
        }
    }
    bool similar(string& a, string& b) {
        int diff = 0;
        for(int i = 0; i < a.size(); i++) {
            if(a[i] != b[i]) diff++;
            if(diff > 2) return false;
        }
        return true;
    }
public:
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        iota(parent, parent + n, 0);
        setCnt = n;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                // 已經在相同集合
                if(find(i) == find(j)) continue;
                // 如果兩者只需交換一個字元就相等，就合併到相同集合
                if(similar(strs[i], strs[j])) {
                    unite(i, j);
                }
            }
        }
        return setCnt;
    }
};

複雜度分析

• 時間複雜度：$O(n^2m)$
• 空間複雜度：$O(n)$