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 <= 2000A[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.
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; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment