# 839. Similar String Groups

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:

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

``````class Solution {
public:
int numSimilarGroups(vector<string>& A) {
int res = 0, n = A.size();
unordered_set<string> visited;
for (string str : A) {
if (visited.count(str)) continue;
++res;
helper(A, str, visited);
}
return res;
}
void helper(vector<string>& A, string& str, unordered_set<string>& visited) {
if (visited.count(str)) return;
visited.insert(str);
for (string word : A) {
if (isSimilar(word, str)) {
helper(A, word, visited);
}
}
}
bool isSimilar(string& str1, string& str2) {
for (int i = 0, cnt = 0; i < str1.size(); ++i) {
if (str1[i] == str2[i]) continue;
if (++cnt > 2) return false;
}
return true;
}
};
``````

``````class Solution {
public:
int numSimilarGroups(vector<string>& A) {
int res = 0, n = A.size();
vector<bool> visited(n);
queue<string> q;
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
visited[i] = true;
++res;
q.push(A[i]);
while (!q.empty()) {
string t = q.front(); q.pop();
for (int j = 0; j < n; ++j) {
if (visited[j]) continue;
int diff = 0;
for (int k = 0; k < A[j].size(); ++k) {
if (t[k] == A[j][k]) continue;
if (++diff > 2) break;
}
if (diff == 0) visited[j] = true;
if (diff == 2) {
visited[j] = true;
q.push(A[j]);
}
}
}
}
return res;
}
};
``````

``````class Solution {
public:
int numSimilarGroups(vector<string>& A) {
int res = 0, n = A.size();
vector<int> root(n);
for (int i = 0; i < n; ++i) root[i] = i;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (!isSimilar(A[i], A[j])) continue;
root[getRoot(root, j)] = i;
}
}
for (int i = 0; i < n; ++i) {
if (root[i] == i) ++res;
}
return res;
}
int getRoot(vector<int>& root, int i) {
return (root[i] == i) ? i : getRoot(root, root[i]);
}
bool isSimilar(string& str1, string& str2) {
for (int i = 0, cnt = 0; i < str1.size(); ++i) {
if (str1[i] == str2[i]) continue;
if (++cnt > 2) return false;
}
return true;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/839

Friend Circles

Accounts Merge

Redundant Connection II

Redundant Connection

Number of Islands II

Graph Valid Tree

Number of Connected Components in an Undirected Graph

https://leetcode.com/problems/similar-string-groups/

https://leetcode.com/problems/similar-string-groups/discuss/200934/My-Union-Find-Java-Solution

https://leetcode.com/problems/similar-string-groups/discuss/282212/Java-two-solutions-BFS-and-Union-Find