LeetCode：839. Similar String Groups相似字符串组（C语言）

小咪咪 2022-10-25 05:48 59阅读 0赞

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

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

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

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

示例 1：

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

示例 2：

输入：strs = \[“omv”,“ovm”\]  
输出：1

提示：

1 <= strs.length <= 100
    1 <= strs[i].length <= 1000
    sum(strs[i].length) <= 2 * 104
    strs[i] 只包含小写字母。
    strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。

备注：

字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/similar-string-groups  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

int find(int *f, int x) { 
        return f[x] == x ? x : (f[x] = find(f, f[x]));
    }
    
    bool check(char *a, char *b, int len) { 
        int num = 0;
        for (int i = 0; i < len; i++) { 
            if (a[i] != b[i]) { 
                num++;
                if (num > 2) { 
                    return false;
                }
            }
        }
        return true;
    }
    
    int numSimilarGroups(char **strs, int strsSize) { 
        int n = strsSize;
        int m = strlen(strs[0]);
        int f[n];
        for (int i = 0; i < n; i++) { 
            f[i] = i;
        }
        for (int i = 0; i < n; i++) { 
            for (int j = i + 1; j < n; j++) { 
                int fi = find(f, i), fj = find(f, j);
                if (fi == fj) { 
                    continue;
                }
                if (check(strs[i], strs[j], m)) { 
                    f[fi] = fj;
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < n; i++) { 
            if (f[i] == i) { 
                ret++;
            }
        }
        return ret;
    }

**运行结果：**  
![在这里插入图片描述][20210131115937540.png_pic_center]

**Notes：**  
参考官方文档：[https://leetcode-cn.com/problems/similar-string-groups/solution/xiang-si-zi-fu-chuan-zu-by-leetcode-solu-8jt9/][https_leetcode-cn.com_problems_similar-string-groups_solution_xiang-si-zi-fu-chuan-zu-by-leetcode-solu-8jt9]

[20210131115937540.png_pic_center]: /images/20221024/78f1febd37734ce9a27728bb2ef73639.png
[https_leetcode-cn.com_problems_similar-string-groups_solution_xiang-si-zi-fu-chuan-zu-by-leetcode-solu-8jt9]: https://leetcode-cn.com/problems/similar-string-groups/solution/xiang-si-zi-fu-chuan-zu-by-leetcode-solu-8jt9/