# 0839. Similar String Groups
###### tags: `Leetcode` `Hard` `Union Find`
Link: https://leetcode.com/problems/similar-string-groups/description/
## 思路
注意每个字符串的长度都是一样的 而且互相是anagram 所以只要看有几个位置字母不一样就行勒
## Code

class Solution {
    int[] fa;
    int size;
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        size = n;
        fa = new int[n];
        for(int i=0; i<n; i++) fa[i] = i;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                if(check(strs[i], strs[j])){
                    combine(i,j);
                }
            }
        }
        return size;
    }
    private boolean check(String s1, String s2){
        int count = 0;
        for(int i=0; i<s1.length(); i++){
            if(s1.charAt(i)!=s2.charAt(i)){
                count++;
                if(count>2) return false;
            }
        }
        return true;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        else return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        size-=1;
        fa[a] = b;
    }
}