Problem
Two stringsĀ X
Ā andĀ Y
Ā are similar if we can swap two letters (in different positions) ofĀ X
, so thatĀ it equalsĀ Y
.
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: ["tars","rats","arts","star"] Output: 2
Note:
A.length <= 2000
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.
Solution: Brute Force + Union Find
Time Complexity: O(n^2 * L)
Space Complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
// Author: Huahua // Running time: 230 ms (<99.08%) class DSU { public: DSU(int size):size_(size), parent_(size), rank_(size) { iota(begin(parent_), end(parent_), 0); } int Find(int n) { if (parent_[n] != n) parent_[n] = Find(parent_[n]); return parent_[n]; } void Union(int x, int y) { int px = Find(x); int py = Find(y); if (px == py) return; if (rank_[py] > rank_[px]) swap(px, py); else if (rank_[py] == rank_[px]) ++rank_[px]; parent_[py] = px; --size_; } int Size() const { return size_; } private: int size_; vector<int> ranks_; vector<int> parent_; }; class Solution { public: int numSimilarGroups(vector<string>& A) { DSU dsu(A.size()); for (int i = 0; i < A.size(); ++i) for (int j = i + 1; j < A.size(); ++j) if (similar(A[i], A[j])) dsu.Union(i, j); return dsu.Size(); } private: bool similar(const string& a, const string& b) { int diff = 0; for (int i = 0; i < a.length(); ++i) if (a[i] != b[i] && ++diff > 2) return false; return true; } }; |