Expressive Words LeetCode solution in C++

1
class Solution {
2
 public:
3
  // Basically get the length of a repeated sequence starting at pointer p.
4
  int getRepeatedLen(string &s, int p) {
5
    int res = 0;
6
    char c = s[p];
7
    while (p < s.size() && s[p] == c) {
8
      res++;
9
      p++;
10
    }
11
    return res;
12
  }
13

14
  // Check if a word t is stretchy. i.e. can we turn word t into word s?
15
  bool isStretchy(string &s, string &t, unordered_set<char> &sMap) {
16
    if (s == t) return true;
17
    if (s.size() < t.size())
18
      return false; // If t is bigger than the original string, return false
19
                    // since we can't take away characters.
20
    int p1 = 0;     // The first pointer will point to a char in our original string.
21
    int p2 = 0;     // The second pointer will point to a char in the word we want
22
                    // to stretch.
23

24
    // Loop though the target string since we know it was to be either the same
25
    // length or longer. i.e. "heeellooo" is longer than "hello".
26
    while (p1 < s.size()) {
27
      if (!sMap.count(t[p2]))
28
        return false;                   // If we find a char in the word we want to stretch that's
29
                                        // not even in our original string, we return false since
30
                                        // we cannot remove chars.
31
      int want = getRepeatedLen(s, p1); // For every new char we encounter we check how
32
                                        // many are in the orignal string.
33
      int have = getRepeatedLen(t, p2);
34
      if (have > want) return false; // Remember can't delete chars.
35
      int needToAdd = want - have;
36
      if (want != have && needToAdd + have < 3)
37
        return false; // If we need to add some chars, we have to also check if
38
                      // the new group size that we create follows our rules of
39
                      // being greater or equal to 3.
40
      p1 += want;     // We don't want to repeat a char again.
41
      p2 += have;     // Same as above but for the other word.
42
    }
43
    return true;
44
  }
45

46
  int expressiveWords(string s, vector<string> &words) {
47
    int res = 0;
48
    unordered_set<char> sMap(s.begin(),
49
                             s.end()); // Useful to know what characters exits in the first place.
50
    // Basically loop through every word in the vector and check if it is
51
    // stretchy.
52
    for (string &w : words) {
53
      if (isStretchy(s, w, sMap)) res++;
54
    }
55
    return res;
56
  }
57
};