Leetcode839相似字符串组

题目分析

从0~n-1遍历单词，每个单词与后续单词进行比较，如果不在同一集合且相似则合并。

遍历两个字符串，记录不同位置的数量，如果不同位置的数量在2个以内则相似，超过了2个则不相似。

求解代码

publicstaticintMAXN=301;publicstaticint[]father=newint[MAXN];publicstaticintsets;publicstaticvoidbuild(intn){for(inti=0;i<n;i++){father[i]=i;}sets=n;}publicstaticintfind(inti){if(i!=father[i]){father[i]=find(father[i]);}returnfather[i];}publicstaticvoidunion(intx,inty){intfx=find(x);intfy=find(y);if(fx!=fy){father[fx]=fy;sets--;}}publicstaticintnumSimilarGroups(String[]strs){intn=strs.length;intm=strs[0].length();build(n);for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){if(find(i)!=find(j)){intdiff=0;for(intk=0;k<m&&diff<3;k++){if(strs[i].charAt(k)!=strs[j].charAt(k)){diff++;}}if(diff==0||diff==2){union(i,j);}}}}returnsets;}