leetcode 困难题 839. Similar String Groups 相似字符串组

Problem: 839. Similar String Groups 相似字符串组

解题过程

并查集，首先去除重复的字符串，然后初始化并查集合，对任意两个字符串，看是否只有两个字符不相同，若是则合并，最后输出根结点个数

Code

class Solution { public: vector<int> arr; int find(int x) { while(arr[x]!=x) x = arr[x]; return x; } void join(int a, int c) { int aa, cc; aa = find(a); cc = find(c); if(aa > cc) arr[aa] = cc; else arr[cc] = aa; } int numSimilarGroups(vector<string>& strs) { unordered_set<string> te; for(string& s : strs) { te.insert(s); } strs.clear(); for(auto && s : te) { strs.push_back(s); } int n = strs.size(); arr.resize(n); for(int i = 0; i < n; i++) { arr[i] = i; } unordered_map<string, int> ump; for(int i = 0; i < n; i++) { ump[strs[i]] = i; } string t0; for(int k = 0; k < n; k++) { for(int i = 0; i < n; i++) { if(i == k) continue; // if(find(k)==find(i)) continue; int s = 0; for(int j = 0; j < strs[k].size(); j++) { if(strs[k][j] != strs[i][j]) { s++; } if(s > 2) { break; } } if(s == 2) { join(i, k); } } } // for(int k = 0; k < n; k++) { // t0 = strs[k]; // for(int i = 0; i < t0.size(); i++) { // for(int j = i + 1; j < t0.size(); j++) { // swap(t0[i], t0[j]); // if(ump.find(t0) != ump.end()) { // join(k, ump[t0]); // } // swap(t0[i], t0[j]); // } // } // } int sum = 0; for(int i = 0; i < n; i++) { if(arr[i] == i) sum++; } return sum; } };