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 <= 20001 <= A[i].length <= 1000A.length * A[i].length <= 20000- All words in
Aconsist of lowercase letters only. - All words in
Ahave 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 }