解法二：BFS

1、思路

• 通过BFS算法计算相相似字符串的集合个数；

• 时间复杂度为 $O(N^2)$ ，空间复杂度为 $O(N)$。

2、代码

class Solution {
public:
    bool isSimilar(string& str1, string& str2)      //判断字符串是否相似
    {
        int diffCount = 0;

        for (int i = 0; i < str1.size(); ++ i)
        {
            if (str1[i] != str2[i])
            {
                diffCount ++ ;
            }
        }

        return diffCount <= 2;
    }

    void bfs(vector<string>& strs, vector<bool>& isVisited, int cur)
    {
        queue<int> q;
        q.push(cur);

        while (!q.empty())
        {
            int i = q.front();
            q.pop();
            isVisited[i] = true;

            for (int j = 0; j < strs.size(); ++ j)
            {
                if (isSimilar(strs[i], strs[j]) && !isVisited[j])
                {
                    q.push(j);
                }
            }
        }
    }

    int numSimilarGroups(vector<string>& strs) {
        vector<bool> isVisited(strs.size());
        int res = 0;

        for (int i = 0; i < strs.size(); ++ i)
        {
            if (!isVisited[i])
            {
                bfs(strs, isVisited, i);
                res ++ ;
            }
        }

        return res;
    }
};

解法二：DFS

1、思路

同上

2、代码

class Solution {
public:
    bool isSimilar(string& str1, string& str2)      //判断字符串是否相似
    {
        int diffCount = 0;

        for (int i = 0; i < str1.size(); ++ i)
        {
            if (str1[i] != str2[i])
            {
                diffCount ++ ;
            }
        }

        return diffCount <= 2;
    }

    void dfs(vector<string>& strs, vector<bool>& isVisited, int i)
    {
        isVisited[i] = true;

        for (int j = 0; j < strs.size(); ++ j)
        {
            if (isSimilar(strs[i], strs[j]) && !isVisited[j])
            {
                dfs(strs, isVisited, j);
            }
        }
    }

    int numSimilarGroups(vector<string>& strs) {
        vector<bool> isVisited(strs.size());
        int res = 0;

        for (int i = 0; i < strs.size(); ++ i)
        {
            if (!isVisited[i])
            {
                dfs(strs, isVisited, i);
                res ++ ;
            }
        }

        return res;
    }
};

解法三：并查集

1、思路

• findFather函数用来寻找字符串的根节点，一旦得知字符串i的根节点就记录到fathers[i]中，相当于压缩了路径；

• 若字符串i与字符串j相似，则在调用isUnion函数后，判断它们是否已经合并到一个子集中，若没有则合并。每完成一次合并，结果group就减1；

• 时间复杂度为 $O(N^2)$ ，空间复杂度为 $O(N)$。

2、代码

class Solution {
public:
    int findFather(vector<int> &fathers, int i)         //找根节点
    {
        if (fathers[i] != i)
        {
            return findFather(fathers, fathers[i]);
        }

        return i;
    }

    bool isUnion(vector<int> &fathers, int i, int j)    //判断是否在一个子集内
    {
        int fatherOfI = findFather(fathers, i);
        int fatherOfJ = findFather(fathers, j);

        if (fatherOfI != fatherOfJ)
        {
            fathers[fatherOfI] = fatherOfJ;
            return true;
        }

        return false;
    }

    bool isSimilar(string &str1, string &str2)          //判断字符串是否相似
    {
        int diffCount = 0;
        for (int i = 0; i < str1.length(); ++ i)
        {
            if (str1[i] != str2[i])
            {
                ++ diffCount;
            }
        }

        return diffCount <= 2;
    }

    int numSimilarGroups(vector<string>& strs) {
        vector<int> fathers(strs.size());
        for (int i = 0; i < strs.size(); ++ i)
        {
            //初始化：每个字符串的相似字符串首先是它自己
            fathers[i] = i;
        }

        int groups = strs.size();
        for (int i = 0; i < strs.size(); ++ i)
        {
            for (int j = 0; j < strs.size(); ++ j)
            {
                //注意：这里必须先判断相似，结果为真后才能进行合并操作
                if (isSimilar(strs[i], strs[j]) && isUnion(fathers, i, j))
                {
                    groups -- ;
                }
            }
        }

        return groups;
    }
};