链接839. 相似字符串组题解class Solution { public: int numSimilarGroups(vectorstring strs) { std::unordered_mapint, std::vectorint graph; for (int i 0; i strs.size(); i) { for (int j 0; j strs.size(); j) { if (is_similar(strs[i], strs[j])) { graph[i].push_back(j); } } } std::vectorbool visited(strs.size(), false); int result 0; for (int i 0; i strs.size(); i) { if (visited[i]) { continue; } bfs(graph, i, visited); result; } return result; } private: bool is_similar(const std::string str1, const std::string str2) { int cnt 0; for (int i 0; i str1.size(); i) { if (str1[i] ! str2[i]) { cnt; } } return cnt 2; } void bfs(std::unordered_mapint, std::vectorint graph, int begin, std::vectorbool visited) { std::queueint que; que.push(begin); visited[begin] true; while (!que.empty()) { auto f que.front(); que.pop(); for (auto neighboard : graph[f]) { if (visited[neighboard]) { continue; } visited[neighboard] true; que.push(neighboard); } } } };class Solution { public: vectorint _rank; vectorint _id; int find(int p) { while(_id[p] ! p) { _id[p] _id[_id[p]]; p _id[p]; } return p; } void union_find(int p, int q) { int root_p find(p); int root_q find(q); if(root_p root_q) { return; } if(_rank[root_p] _rank[root_q]) { _id[root_p] root_q; } else if(_rank[root_q] _rank[root_p]) { _id[root_q] root_p; } else { _id[root_p] root_q; _rank[root_q] 1; } } bool is_connected(int p, int q) { return find(p) find(q); } int get_size() { int cnt 0; for(int i 0; i _id.size(); i) { if(_id[i] i) { cnt; } } return cnt; } bool check(const std::string s1, const std::string s2) { int cnt 0; for(int i 0; i s1.size(); i) { if(s1[i] ! s2[i]) { cnt; } if(cnt 2) { return false; } } return true; } int numSimilarGroups(vectorstring strs) { if(strs.size() 0) { return 0; } _rank.resize(strs.size(), 1); _id.resize(strs.size()); // 每个字符串自己为一个节点 for(int i 0; i strs.size(); i) { _id[i] i; } //判断一个字符串是否与其他的字符串满足一个组的条件 for(int i 0; i strs.size(); i) { for(int j i1; j strs.size(); j) { // 如果已经在一个组了 if(is_connected(i, j)) { continue; } // 检测是否满足规则 if(check(strs[i], strs[j])) { union_find(i, j); } } } return get_size(); } };
