Lintcode 1430. Similar String Groups

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?

Example

Example 1:

Input: ["tars","rats","arts","star"]
Output: 2

Example 2:

Input: ["omv","ovm"]
Output: 1

Clarification

Anagram: a new word formed by changing the position (order) of the letters in a string.

Notice

1.A.length <= 2000
2.A[i].length <= 1000
3.A.length * A[i].length <= 20000
4.All words in A consist of lowercase letters only.

5.All words in A have the same length and are anagrams of each other. 

Solution:

Union-Find. For each of the two words in the list, if they are similar, connect them into the same connected components. In the end, we need to count number of cc. 

Code (Java):

public class Solution {
    /**
     * @param A: a string array
     * @return: the number of groups 
     */
    public int numSimilarGroups(String[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        
        UF uf = new UF(A);
        
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                if (isSimilar(A[i], A[j])) {
                    uf.connect(A[i], A[j]);
                }
            }
        }
        
        return uf.getNumCC();
    }
    
    private boolean isSimilar(String s1, String s2) {
        int first = -1;
        int second = -1;
        
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            
            if (c1 == c2) {
                continue;
            }
            
            if (first == -1) {
                first = i;
            } else if (second == -1) {
                second = i;
            } else {
                return false;
            }
        }
        
        if (first == -1 && second == -1) {
            return true;
        }
        
        if (s1.charAt(first) == s2.charAt(second) && s1.charAt(second) == s2.charAt(first)) {
            return true;
        }
        
        return false;
    }
}

class UF {
    private Map<String, String> parents;
    private int numCC;
    
    public UF (String[] A) {
        parents = new HashMap<>();
        
        for (String a : A) {
            parents.put(a, a);
        }
        
        numCC = parents.size();
    }
    
    public String find(String a) {
        String root = a;
        
        while (!root.equals(parents.get(root))) {
            root = parents.get(root);
        }
        
        // path compression
        while (!root.equals(a)) {
            String parent = parents.get(a);
            parents.put(a, root);
            a = parent;
        }
        
        return root;
    }
    
    public void connect(String a, String b) {
        String pa = find(a);
        String pb = find(b);
        
        if (!pa.equals(pb)) {
            parents.put(pa, pb);
            numCC--;
        }
    }
    
    public int getNumCC() {
        return numCC;
    }
}