题目描述

如果我们交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，”tars” 和 “rats” 是相似的 (交换 0 与 2 的位置)； “rats” 和 “arts” 也是相似的，但是 “star” 不与 “tars”，”rats”，或 “arts” 相似。

总之，它们通过相似性形成了两个关联组：{“tars”, “rats”, “arts”} 和 {“star”}。注意，”tars” 和 “arts” 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

我们给出了一个不包含重复的字符串列表 A。列表中的每个字符串都是 A 中其它所有字符串的一个字母异位词。请问 A 中有多少个相似字符串组？

样例

输入：[“tars”,”rats”,”arts”,”star”]
输出：2

算法1

(并查集) $O(n^2m)$

C++ 代码

class Solution {
public:
    bool isfim(const string &a,const string &b)
    {
         if (a.size() != b.size()) return false;
         int diff = 0;
         for(int i =  0; i < a.size(); i ++ )
         {
             if (a[i] != b[i])
             {
                  ++diff;
                  if (diff > 2) return false;
             }
         }

          return true;

    }

    int findfather(int i)
    {

       if (i != f[i]) f[i] = findfather(f[i]); 

       return f[i];




    }
    vector<int> f; // 构建并查集 
    int numSimilarGroups(vector<string>& A) {
         int n = A.size();
         f.resize(n);

         for(int i = 0; i < n ; i++) f[i] = i; //初始化并查集

         for(int i = 0; i < n - 1 ; i++) //遍历
         {
            for(int j = i+1; j < n; j++)
            {
                if(isfim(A[i],A[j])) // judge

                    f[findfather(i)] = findfather(j);


            }

         }
         unordered_set<int> s;

         for(int i = 0 ; i < n ; i ++)
           if(f[i] == i) s.insert(i);
           return s.size();
    }
};

这里注意一定要把f[x] 的值洗出来，我们需要确定每一个字符串的father具体是谁
这样做可以将查找根节点的路径压缩，虽然破坏了并查集本来的结构，但是对于本题来说效果更好