Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/839.html

839. Similar String Groups (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 A of strings.  Every string in A is an anagram of every other string in A.  How many groups are there?

 

Example 1:

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

 

Constraints:

  • 1 <= A.length <= 2000
  • 1 <= A[i].length <= 1000
  • A.length * A[i].length <= 20000
  • All words in A consist of lowercase letters only.
  • All words in A have the same length and are anagrams of each other.
  • The judging time limit has been increased for this question.

Related Topics:
Depth-first Search, Union Find, Graph

Solution 1. UnionFind

// OJ: https://leetcode.com/problems/similar-string-groups/
// Time: O(NW)
// Space: O(N)
class UnionFind {
    vector<int> id;
    int size;
public:
    UnionFind(int N) : id(N), size(N) {
        iota(begin(id), end(id), 0);
    }
    int find(int x) {
        return id[x] == x ? x : (id[x] = find(id[x]));
    }
    void connect(int x, int y) {
        int p = find(x), q = find(y);
        if (p == q) return;
        id[p] = q;
        --size;
    }
    int getSize() { return size; }
};
class Solution {
    bool similar(string &a, string &b) {
        int cnt = 0;
        for (int i = 0; i < a.size(); ++i) {
            if ((cnt += (a[i] != b[i])) > 2) return false;
        }
        return cnt == 2 || cnt == 0;
    }
public:
    int numSimilarGroups(vector<string>& A) {
        int N = A.size();
        UnionFind uf(N);
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                if (similar(A[i], A[j])) uf.connect(i, j);
            }
        }
        return uf.getSize();
    }
};
  • class Solution {
        public int numSimilarGroups(String[] A) {
            Map<String, Integer> stringGroupMap = new HashMap<String, Integer>();
            Map<Integer, Set<String>> groupSetMap = new HashMap<Integer, Set<String>>();
            int length = A.length;
            for (int i = 0; i < length; i++) {
                if (stringGroupMap.containsKey(A[i]))
                    continue;
                stringGroupMap.put(A[i], i);
                Set<String> set = new HashSet<String>();
                set.add(A[i]);
                groupSetMap.put(i, set);
            }
            for (int i = 0; i < length; i++) {
                String str1 = A[i];
                for (int j = i + 1; j < length; j++) {
                    String str2 = A[j];
                    if (difference(str1, str2) <= 2) {
                        int group1 = stringGroupMap.get(str1);
                        int group2 = stringGroupMap.get(str2);
                        if (group1 == group2)
                            continue;
                        Set<String> set1 = groupSetMap.get(group1);
                        Set<String> set2 = groupSetMap.get(group2);
                        if (group1 < group2) {
                            set1.addAll(set2);
                            for (String str : set1)
                                stringGroupMap.put(str, group1);
                            groupSetMap.put(group1, set1);
                            groupSetMap.remove(group2);
                        } else {
                            set2.addAll(set1);
                            for (String str : set2)
                                stringGroupMap.put(str, group2);
                            groupSetMap.put(group2, set2);
                            groupSetMap.remove(group1);
                        }
                    }
                }
            }
            return groupSetMap.size();
        }
    
        public int difference(String str1, String str2) {
            int difference = 0;
            int length = str1.length();
            for (int i = 0; i < length; i++) {
                if (str1.charAt(i) != str2.charAt(i))
                    difference++;
            }
            return difference;
        }
    }
    
    ############
    
    class Solution {
        private int[] p;
    
        public int numSimilarGroups(String[] strs) {
            int n = strs.length;
            p = new int[n];
            for (int i = 0; i < n; ++i) {
                p[i] = i;
            }
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    if (check(strs[i], strs[j])) {
                        p[find(i)] = find(j);
                    }
                }
            }
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                if (i == find(i)) {
                    ++ans;
                }
            }
            return ans;
        }
    
        private int find(int x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }
    
        private boolean check(String a, String b) {
            int cnt = 0;
            for (int i = 0; i < a.length(); ++i) {
                if (a.charAt(i) != b.charAt(i)) {
                    ++cnt;
                }
            }
            return cnt <= 2;
        }
    }
    
  • // OJ: https://leetcode.com/problems/similar-string-groups/
    // Time: O(NW)
    // Space: O(N)
    class UnionFind {
        vector<int> id;
        int size;
    public:
        UnionFind(int N) : id(N), size(N) {
            iota(begin(id), end(id), 0);
        }
        int find(int x) {
            return id[x] == x ? x : (id[x] = find(id[x]));
        }
        void connect(int x, int y) {
            int p = find(x), q = find(y);
            if (p == q) return;
            id[p] = q;
            --size;
        }
        int getSize() { return size; }
    };
    class Solution {
        bool similar(string &a, string &b) {
            int cnt = 0;
            for (int i = 0; i < a.size(); ++i) {
                if ((cnt += (a[i] != b[i])) > 2) return false;
            }
            return cnt == 2 || cnt == 0;
        }
    public:
        int numSimilarGroups(vector<string>& A) {
            int N = A.size();
            UnionFind uf(N);
            for (int i = 0; i < N; ++i) {
                for (int j = i + 1; j < N; ++j) {
                    if (similar(A[i], A[j])) uf.connect(i, j);
                }
            }
            return uf.getSize();
        }
    };
    
  • class Solution:
        def numSimilarGroups(self, strs: List[str]) -> int:
            def find(x):
                if p[x] != x:
                    p[x] = find(p[x])
                return p[x]
    
            n, l = len(strs), len(strs[0])
            p = list(range(n))
            for i in range(n):
                for j in range(i + 1, n):
                    if sum(strs[i][k] != strs[j][k] for k in range(l)) <= 2:
                        p[find(i)] = find(j)
            return sum(i == find(i) for i in range(n))
    
    ############
    
    class Solution(object):
        def numSimilarGroups(self, strs):
            """
            :type strs: List[str]
            :rtype: int
            """
            N = len(strs)
            dsu = DSU(N)
            for i in range(N):
                for j in range(i + 1, N):
                    if self.isSimilar(strs[i], strs[j]):
                        dsu.union(i, j)
            return dsu.regions()
                
        def isSimilar(self, str1, str2):
            count = 0
            for i in range(len(str1)):
                if str1[i] != str2[i]:
                    count += 1
            return count == 2 or count == 0
    
    class DSU:
        def __init__(self, N):
            self.par_ = range(N + 1)
            self.regions_ = N
    
        def find(self, x):
            if x != self.par_[x]:
                self.par_[x] = self.find(self.par_[x])
            return self.par_[x]
        
        def union(self, x, y):
            px = self.find(x)
            py = self.find(y)
            if px == py:
                return
            self.par_[px] = py
            self.regions_ -= 1
        
        def regions(self):
            return self.regions_
    
  • func numSimilarGroups(strs []string) int {
    	n := len(strs)
    	p := make([]int, n)
    	for i := range p {
    		p[i] = i
    	}
    	check := func(a, b string) bool {
    		cnt := 0
    		for i := range a {
    			if a[i] != b[i] {
    				cnt++
    			}
    		}
    		return cnt <= 2
    	}
    	var find func(x int) int
    	find = func(x int) int {
    		if p[x] != x {
    			p[x] = find(p[x])
    		}
    		return p[x]
    	}
    	for i := 0; i < n; i++ {
    		for j := i + 1; j < n; j++ {
    			if check(strs[i], strs[j]) {
    				p[find(i)] = find(j)
    			}
    		}
    	}
    	ans := 0
    	for i := 0; i < n; i++ {
    		if i == find(i) {
    			ans++
    		}
    	}
    	return ans
    }
    

All Problems

All Solutions