Skip to content

1096. Brace Expansion II

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
 public:
  vector<string> braceExpansionII(string expression) {
    return dfs(expression, 0, expression.length() - 1);
  }

 private:
  vector<string> dfs(const string& expression, int s, int e) {
    set<string> ans;
    vector<vector<string>> groups{{}};
    int layer = 0;
    int left = 0;

    for (int i = s; i <= e; ++i)
      if (expression[i] == '{' && ++layer == 1)
        left = i + 1;
      else if (expression[i] == '}' && --layer == 0)
        merge(groups, dfs(expression, left, i - 1));
      else if (expression[i] == ',' && layer == 0)
        groups.push_back({});
      else if (layer == 0)
        merge(groups, {string(1, expression[i])});

    for (const vector<string>& group : groups)
      for (const string& word : group)
        ans.insert(word);

    return {ans.begin(), ans.end()};
  }

  void merge(vector<vector<string>>& groups, const vector<string> group) {
    if (groups.back().empty()) {
      groups[groups.size() - 1] = group;
      return;
    }

    vector<string> mergedGroup;

    for (auto& word1 : groups.back())
      for (auto& word2 : group)
        mergedGroup.push_back(word1 + word2);

    groups[groups.size() - 1] = mergedGroup;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
  public List<String> braceExpansionII(String expression) {
    return dfs(expression, 0, expression.length() - 1);
  }

  private List<String> dfs(final String expression, int s, int e) {
    TreeSet<String> ans = new TreeSet<>();
    List<List<String>> groups = new ArrayList<>();
    groups.add(new ArrayList<>());
    int layer = 0;
    int left = 0;

    for (int i = s; i <= e; ++i)
      if (expression.charAt(i) == '{' && ++layer == 1)
        left = i + 1;
      else if (expression.charAt(i) == '}' && --layer == 0)
        merge(groups, dfs(expression, left, i - 1));
      else if (expression.charAt(i) == ',' && layer == 0)
        groups.add(new ArrayList<>());
      else if (layer == 0)
        merge(groups, new ArrayList<>(List.of(String.valueOf(expression.charAt(i)))));

    for (final List<String> group : groups)
      for (final String word : group)
        ans.add(word);

    return new ArrayList<>(ans);
  }

  void merge(List<List<String>> groups, List<String> group) {
    if (groups.get(groups.size() - 1).isEmpty()) {
      groups.set(groups.size() - 1, group);
      return;
    }

    List<String> mergedGroup = new ArrayList<>();

    for (final String word1 : groups.get(groups.size() - 1))
      for (final String word2 : group)
        mergedGroup.add(word1 + word2);

    groups.set(groups.size() - 1, mergedGroup);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def braceExpansionII(self, expression: str) -> list[str]:
    def merge(groups: list[list[str]], group: list[str]) -> None:
      if not groups[-1]:
        groups[-1] = group
        return

      groups[-1] = [word1 + word2 for word1 in groups[-1]
                    for word2 in group]

    def dfs(s: int, e: int) -> list[str]:
      groups = [[]]
      layer = 0

      for i in range(s, e + 1):
        c = expression[i]
        if c == '{':
          layer += 1
          if layer == 1:
            left = i + 1
        elif c == '}':
          layer -= 1
          if layer == 0:
            group = dfs(left, i - 1)
            merge(groups, group)
        elif c == ',' and layer == 0:
          groups.append([])
        elif layer == 0:
          merge(groups, [c])

      return sorted(list({word for group in groups for word in group}))

    return dfs(0, len(expression) - 1)