# 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 braceExpansionII(string expression) { return dfs(expression, 0, expression.length() - 1); } private: vector dfs(const string& expression, int s, int e) { set ans; vector> 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& group : groups) for (const string& word : group) ans.insert(word); return {ans.begin(), ans.end()}; } void merge(vector>& groups, const vector group) { if (groups.back().empty()) { groups[groups.size() - 1] = group; return; } vector 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 braceExpansionII(String expression) { return dfs(expression, 0, expression.length() - 1); } private List dfs(final String expression, int s, int e) { TreeSet ans = new TreeSet<>(); List> 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<>(Arrays.asList(String.valueOf(expression.charAt(i))))); for (final List group : groups) for (final String word : group) ans.add(word); return new ArrayList<>(ans); } void merge(List> groups, List group) { if (groups.get(groups.size() - 1).isEmpty()) { groups.set(groups.size() - 1, group); return; } List 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)