学习记录

LeeCodeJava并查集

839.相似字符串组

思路:

使用双重循环遍历字符串组,将相似的字符串加入并查集,最后遍历查找根点的个数,即为结果.

我的代码:

class Solution {
    public int numSimilarGroups(String[] strs) {
        UnionFind unionFind=new UnionFind(strs.length);
        for (int i = 0; i < strs.length; i++) {
            for (int j = i; j < strs.length; j++) {
                if(similar(strs[i],strs[j])){
                    unionFind.union(i,j);
                }
            }
        }
        int count=0;
        for (int i = 0; i < unionFind.parents.length; i++) {
            if(unionFind.parents[i]==i){
                count++;
            }
        }
        return count;
    }
    //这个方法极其巧妙.
    public boolean similar(String a,String b){
        int count=0;
        for (int i = 0; i < a.length(); i++) {
            if(a.charAt(i)!=b.charAt(i)){
                count++;
            }
            if(count==3){
                return false;
            }
        }
        return count != 1;
    }
}
class UnionFind{
    int[] parents;
    int[] sizes;
    int n;
    public UnionFind(int n) {
        this.n = n;
        parents=new int[n];
        sizes=new int[n];
        Arrays.fill(sizes,1);
        for (int i = 0; i < parents.length; i++) {
            parents[i]=i;
        }
    }
    public boolean union(int a,int b){
        a=findParent(a);
        b=findParent(b);
        if(a==b){return false;}
        //a短,b长
        if(sizes[a]>sizes[b]){
            int temp=a;
            a=b;
            b=temp;
        }
        parents[a]=b;
        sizes[b]+=sizes[a];
        return true;
    }
    public int findParent(int a){
        if(parents[a]==a){
            return a;
        }else {
            return findParent(parents[a]);
        }
    }
    public boolean connected(int a,int b){
        return findParent(a)==findParent(b);
    }
}

结论:

AC,这个已经是最高的并查集速度了.值得注意的是利用判断同一位置不同值的出现次数的方法来判断是否是只易位了一个字符,相当巧妙.值得单独为其增添一个代码块.

判断字符串只易位了一个字母:

public boolean similar(String a,String b){
        int count=0;
        for (int i = 0; i < a.length(); i++) {
            if(a.charAt(i)!=b.charAt(i)){
                count++;
            }
            if(count==3){
                return false;
            }
        }
        return count != 1;
    }