Brace Expansion II LeetCode solution in C++

1
class Solution {
2
 public:
3
  void getUnion(vector<string> &a, const vector<string> &b) {
4
    if (!a.size()) {
5
      a = b;
6
      return;
7
    }
8
    for (const auto &str_b : b) {
9
      bool found = false;
10
      for (const auto &str_a : a) {
11
        if (str_a == str_b) {
12
          found = true;
13
          break;
14
        }
15
      }
16
      if (!found) a.push_back(str_b);
17
    }
18
  }
19
  void getComb(vector<string> &a, const vector<string> &b) {
20
    if (!a.size()) {
21
      a = b;
22
      return;
23
    }
24
    vector<string> tmp;
25
    for (const auto &str_a : a) {
26
      for (const auto &str_b : b) {
27
        tmp.push_back(str_a + str_b);
28
      }
29
    }
30
    a = tmp;
31
  }
32
  vector<string> braceExpansionII(string expression) {
33
    if (expression.size() == 0) return {};
34
    if (expression.size() == 1) return {expression};
35
    int n = expression.size();
36
    vector<string> ans;
37
    vector<string> processing_str;
38
    int in_brace = 0;
39
    string partial_str{};
40

41
    for (int i = 0; i < n; ++i) {
42
      if (expression[i] == '{') {
43
        if (in_brace) partial_str += expression[i];
44
        in_brace++;
45
      } else if (expression[i] == '}') {
46
        in_brace--;
47
        if (in_brace) partial_str += expression[i];
48
        if (!in_brace) {
49
          getComb(processing_str, braceExpansionII(partial_str));
50
          partial_str.clear();
51
        }
52
      } else if (in_brace == 0 && expression[i] == ',') {
53
        getUnion(ans, processing_str);
54
        processing_str.clear();
55
        partial_str.clear();
56
      } else if (in_brace == 0) {
57
        std::string tmp = "";
58
        while (i < n && expression[i] >= 'a' && expression[i] <= 'z') tmp += expression[i++];
59
        --i;
60
        getComb(processing_str, {tmp});
61
      } else {
62
        partial_str += expression[i];
63
      }
64
    }
65
    getUnion(ans, processing_str);
66
    sort(ans.begin(), ans.end());
67
    return ans;
68
  }
69
};