839. Similar String Groups

839. Similar String Groups

Question

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 1:

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

Note:

• A.length <= 2000
• A[i].length <= 1000
• A.length * A[i].length <= 20000
• All words in A consist of lowercase letters only.
• All words in A have the same length and are anagrams of each other.
• The judging time limit has been increased for this question.

Solution

• Method 1: Union Find Set

  class Solution {
      private int[] uf;
      private int[] rank;
      public int numSimilarGroups(String[] A) {
          uf = new int[A.length];
          rank = new int[A.length];
          for(int i = 0; i < A.length; i++){
              uf[i] = i;
          }
          for(int i = 0; i < A.length; i++){
              for(int j = i + 1; j < A.length; j++){
                  if(i == j) continue;
                  else if(connected(A[i], A[j])){
                      union(i, j);
                  }
              }
          }
          int res = 0;
          for(int i = 0; i < A.length; i++){
              if(uf[i] == i) res++;
          }
          return res;
      }
      private int find(int a){
          if(a != uf[a]){
              uf[a] = find(uf[a]);
          }
          return uf[a];
      }
      private void union(int a, int b){
          int p = find(a);
          int q = find(b);
          if(q == p) return;
          if(rank[p] < rank[q]){
              uf[p] = q;
              rank[q] = Math.max(rank[q], rank[p] + 1);
          }else{
              uf[q] = p;
              rank[p] = Math.max(rank[p], rank[q] + 1);
          }
      }
      private boolean connected(String a, String b){
          if(a.equals(b)) return true;
          char[] arrA = a.toCharArray();
          char[] arrB = b.toCharArray();
          int diff = 0;
          for(int i = 0; i < arrA.length; i++){
              if(arrA[i] != arrB[i]) diff++;
              if(diff > 2) return false;
          }
          return diff == 0 || diff == 2;
      }
  }