Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 28

Description

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. Also two strings X and Y are similar if they are equal.

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 strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?

Example 1:

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

Example 2:

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

Constraints:

• 1 <= strs.length <= 300
• 1 <= strs[i].length <= 300
• strs[i] consists of lowercase letters only.
• All words in strs have the same length and are anagrams of each other.

Solution

struct UnionSet {
  vector<int> parent;
public:
  UnionSet(int size): parent(size) {
    for(int i = 0; i < size; ++i) {
      parent[i] = i;
    }
  }

  int find(int x) {
    if(parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }

  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    parent[x] = y;
  }
};
class Solution {
  int len;
  bool isSimilar(const string &a, const string &b) {
    int pos1 = -1;
    int pos = 0;
    while(pos < len && a[pos] == b[pos]) {
      pos += 1;
    }
    if(pos == len) return true;
    pos1 = pos;
    pos += 1;
    while(pos < len && a[pos] == b[pos]) {
      pos += 1;
    }
    if(pos == len) return false;
    if(a[pos1] != b[pos] || b[pos1] != a[pos]) return false;
    pos += 1;
    while(pos < len && a[pos] == b[pos]) {
      pos += 1;
    }
    return pos == len;
  }
public:
  int numSimilarGroups(vector<string>& strs) {
    UnionSet us(strs.size());
    len = strs.front().length();

    int answer = strs.size();
    for(int i = 0; i < strs.size() - 1; ++i) {
      for(int j = i + 1; j < strs.size(); ++j) {
        if(isSimilar(strs[i], strs[j]) && us.find(i) != us.find(j)) {
          us.merge(i, j);
          answer -= 1;
        }
      }
    }

    return answer;
  }
};

// Accepted
// 77/77 cases passed (30 ms)
// Your runtime beats 80.63 % of cpp submissions
// Your memory usage beats 76.83 % of cpp submissions (10.1 MB)