Home Coding Leetcode Hard

⭐️⭐️⭐️

# 題目敘述

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

# 解題思路

遍歷整個陣列將相似的字串組合為群組，最後輸出群組的數量。

比對字串相似的方法，如果差異的字元數量大於 2，則兩字串不相似。

Union Find 的部分可以參考這個文章 連結

# Solution

class Solution {
public:
    vector<int> parent, rank;
    int res;
    bool similar(string& s1, string& s2) {
        if (s1 == s2) return true;
        int diff = 0;
        for (int i=0; i<s1.size(); i++) {
            if (s1[i] != s2[i]) {
                diff++;
                if (diff > 2) return false;
            }
        }
        return diff == 2;
    }
    int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    void unionSet(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] > rank[py]) parent[py] = px;
        else if (rank[px] < rank[py]) parent[px] = py;
        else {
            parent[py] = px;
            rank[px] ++;
        }
        res--;
    }
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        res = n;
        parent.resize(n);
        rank.resize(n);
        for (int i=0; i<n; i++) parent[i] = i;
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                if (similar(strs[i], strs[j])) unionSet(i, j);
            }
        }
        return res;
    }
};
class Solution {
    class UnionFind {
        int[] parent, rank;
        int count;
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return false;
            }
            if (rank[rootX] < rank[rootY]) {
                int temp = rootX;
                rootX = rootY;
                rootY = temp;
            }
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
            count--;
            return true;
        }
        public int getCount() {
            return count;
        }
    }
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isSimilar(strs[i], strs[j])) {
                    uf.union(i, j);
                }
            }
        }
        return uf.getCount();
    }
    private boolean isSimilar(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
                if (diff > 2) {
                    return false;
                }
            }
        }
        return diff == 2;
    }
}
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        self.count -= 1
        return True
class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        def is_similar(s1, s2):
            if s1 == s2:
                return True
            diff = 0
            for c1, c2 in zip(s1, s2):
                if c1 != c2:
                    diff += 1
                    if diff > 2:
                        return False
            return diff == 2
        n = len(strs)
        uf = UnionFind(n)
        for i in range(n):
            for j in range(i + 1, n):
                if is_similar(strs[i], strs[j]):
                    uf.union(i, j)
        return uf.count