839. Similar String Groups

Hard (Khó) C++ Python 🔗 Xem trên LeetCode

📋 Đề Bài

Two strings, X and Y, are considered similar if either they are identical or we can make them equivalent by swapping at most two letters (in distinct positions) within the string X.

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 <= 300
  • 1 <= strs[i].length <= 300
  • strs[i] consists of lowercase letters only.
  • All words in strs have the same length and are anagrams of each other.

🧠 Thuật Toán & Kỹ Thuật

Union Find (Tập hợp rời rạc)String (Chuỗi)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0839-similar-string-groups.cpp 
class Solution {
private:
    vector<int> parent;
    int group;
    
public:
    int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]);
        }    
        return parent[u];
    }
    
    void _union(int u, int v) {
        u = find(u);
        v = find(v);
        
        if (u != v) {
            parent[u] = v;
            group--;
        }
    }
    
    bool isSimilar(string a, string b) {
        int cnt = 0;
        int n = a.size();
        
        for (int i = 0; i < n; ++i) {
            cnt += a[i] != b[i];
            if (cnt > 2) {
                return false;
            }
        }
        
        return cnt == 0 or cnt == 2;
    }
    
    int numSimilarGroups(vector<string>& strs) {
        int n = strs.size();
        this->group = n;
        parent.resize(group);
        
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
        
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (isSimilar(strs[i], strs[j])) {
                    _union(i, j);
                }
            }
        }
        
        return group;
    }
};
Python 0839-similar-string-groups.py 
class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        m, n = len(strs), len(strs[0])
        self.parent = [u for u in range(m)]
        self.group = m
    
        def find(u):
            if u != self.parent[u]:
                self.parent[u] = find(self.parent[u])
            return self.parent[u]
        
        def join(u, v):
            pu = find(u)
            pv = find(v)
            if pu != pv:
                self.parent[pu] = pv
                self.group -= 1
                
        def isSimilar(a, b):
            cnt = 0
            
            for i in range(n):
                if a[i] != b[i]:
                    cnt += 1
                if cnt > 2:
                    return False
                
            return cnt == 0 or cnt == 2
                
        
        for i in range(m):
            for j in range(i + 1, m):
                a = strs[i]
                b = strs[j]
                if isSimilar(a, b):
                    join(i, j)
                    
        return self.group