Keyboard Row LeetCode solution in C++

1
class DSU {
2
  vector<int> parent, size;
3

4
  vector<int> Q{'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p',
5
                'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'};
6
  vector<int> A{'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l',
7
                'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L'};
8
  vector<int> Z{'z', 'x', 'c', 'v', 'b', 'n', 'm', 'Z', 'X', 'C', 'V', 'B', 'N', 'M'};
9

10
 public:
11
  DSU() {
12
    for (int i = 0; i < 123; i++) parent.push_back(i), size.push_back(1);
13
    for (int i = 0; i < Q.size() - 1; i++) findUnion(Q[i], Q[i + 1]);
14
    for (int i = 0; i < A.size() - 1; i++) findUnion(A[i], A[i + 1]);
15
    for (int i = 0; i < Z.size() - 1; i++) findUnion(Z[i], Z[i + 1]);
16
  }
17

18
  int findParent(int x) {
19
    if (x == parent[x]) return x;
20
    return parent[x] = findParent(parent[x]);
21
  }
22

23
  void findUnion(int a, int b) {
24
    a = findParent(a);
25
    b = findParent(b);
26
    if (a != b)
27
      if (size[b] > size[a]) swap(a, b);
28
    parent[b] = a, size[a] += size[b];
29
  }
30
};
31

32
class Solution {
33
 public:
34
  vector<string> findWords(vector<string> &words) {
35
    int n = words.size();
36
    DSU dsu;
37
    vector<string> ans;
38
    for (int i = 0; i < n; i++) {
39
      int ss = words[i].size();
40
      string s = words[i];
41
      if (ss == 1) {
42
        ans.push_back(s);
43
        continue;
44
      }
45

46
      bool sameSet = true;
47
      for (int j = 0; j < ss - 1; j++)
48
        if (dsu.findParent(s[j]) != dsu.findParent(s[j + 1])) {
49
          sameSet = false;
50
          break;
51
        }
52
      if (sameSet) ans.push_back(s);
53
    }
54
    return ans;
55
  }
56
};