LeetCode-839. Similar String Groups(相似字符串组)

相似字符串组

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

例如,"tars""rats" 是相似的 (交换 02 的位置); "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. 1 <= strs.length <= 100
  2. 1 <= strs[i].length <= 1000
  3. sum(strs[i].length) <= 2 * 104
  4. strs[i] 只包含小写字母。
  5. strs 中的所有单词都具有相同的长度,且是彼此的字母异位词。

备注:
字母异位词(anagram),一种把某个字符串的字母的位置(顺序)加以改换所形成的新词。

Similar String Groups

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?
Example 1:

Input: strs = ["tars","rats","arts","star"]
Output: 2

Example 2:

Input: strs = ["omv","ovm"]
Output: 1

Constraints:

  • 1 <= strs.length <= 100
  • 1 <= strs[i].length <= 1000
  • sum(strs[i].length) <= 2 * 104
  • strs[i] consists of lowercase letters only.
  • All words in strs have the same length and are anagrams of each other.

并查集
相似字符串的意思是:通过交换字符串str1某两个字母的位置,使得str1str2相同。注意,这里只能交换两个字母的位置
具体做法是,将每个字符串当做图的一个节点,当两个字符串相似时,就将两个结点之间画一条边,如此,相似的字符串组就形成了一个连通图,连通区域的个数就是我们想要的答案。

class Solution {
   public:
    int n;
    int numSimilarGroups(vector<string>& strs) {
        n = strs.size();
        UnionFind unionFind(n);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (isSimilar(strs[i], strs[j])) {
                    unionFind.connect(i, j);
                }
            }
        }

        return unionFind.getRegions();
    }

   private:
    bool isSimilar(string str1, string str2) {
        int count = 0;
        for (int i = 0; i < str1.size(); ++i) {
            if (str1[i] != str2[i]) {
                count++;
            }
        }
        return count == 2 || count == 0;
    }
    class UnionFind {
       private:
        vector<int> parent;
        int regions;

       public:
        UnionFind(int n) : parent(n), regions(n) {
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
            }
        }
        int root(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        bool isConnected(int x, int y) { return root(x) == root(y); }
        void connect(int p, int q) {
            if (isConnected(p, q)) {
                return;
            }
            parent[root(p)] = root(q);
            regions--;
        }
        int getRegions() { return regions; }
    };
};
上一篇:Kafka – kafka consumer


下一篇:第 30 题:如何理解基数排序?