DDSA Solutions

1096. Brace Expansion II

HardView on LeetCode
StringStackBreadth-First SearchRecursion

Problem Overview

Braces encode a small grammar: a comma list is a union, and two expressions written next to each other are concatenated in every combination.

Intuition

Braces encode a small grammar: a comma list is a union, and two expressions written next to each other are concatenated in every combination. Nested braces are just the same grammar on a smaller span, so a recursive parse builds the set of words and a final sort puts them in order.

Algorithm

  1. 1Scan a span from left to right, tracking brace depth.
  2. 2At depth 0, a letter is a one-word set and is concatenated onto the current group.
  3. 3At depth 0, a comma starts a new group that will be unioned with the others.
  4. 4A matching brace pair is parsed recursively and concatenated onto the current group.
  5. 5Union the groups with a hash set so duplicate words collapse.
  6. 6Sort the top-level set once and return it.

Example Walkthrough

Input: expression = "{a,b}{c,{d,e}}"

  1. 1.{a,b} is the union of a and b.
  2. 2.{c,{d,e}} is the union of c, d, and e.
  3. 3.Concatenating the two sets produces ac, ad, ae, bc, bd, and be.

Output: ["ac","ad","ae","bc","bd","be"]

Common Pitfalls

  • •Adjacent expressions are a product, not a union.
  • •Overlapping options such as {a,ab} and {b} can create the same word twice; keep a set.
  • •Only the final list must be sorted. Sorting every nested group is extra work.
  • •Match braces by depth so a comma inside nested braces does not split the outer expression.
1096.cs
C#
// Approach: The grammar is union inside braces and concatenation of neighbors.
// Parse with recursion on matching braces. Each level keeps the options seen
// so far in a hash set, multiplies adjacent pieces, and unions comma-separated
// pieces. Sort once at the end, since only the final list must be ordered.
// Complexity: O(U * L) to build the words plus O(U log U) to sort, where U is
// the number of distinct words and L is the longest word. Output size dominates.
public class Solution
{
    public IList<string> BraceExpansionII(string expression)
    {
        var words = Expand(expression, 0, expression.Length - 1);
        var ans = new List<string>(words);
        ans.Sort(StringComparer.Ordinal);
        return ans;
    }

    private HashSet<string> Expand(string expression, int s, int e)
    {
        var groups = new List<HashSet<string>> { new HashSet<string>() };
        int layer = 0;
        int left = 0;

        for (int i = s; i <= e; i++)
        {
            char c = expression[i];
            if (c == '{' && ++layer == 1)
            {
                left = i + 1;
            }
            else if (c == '}' && --layer == 0)
            {
                Merge(groups, Expand(expression, left, i - 1));
            }
            else if (c == ',' && layer == 0)
            {
                groups.Add(new HashSet<string>());
            }
            else if (layer == 0)
            {
                Merge(groups, new HashSet<string> { c.ToString() });
            }
        }

        var ans = new HashSet<string>();
        foreach (var group in groups)
            ans.UnionWith(group);
        return ans;
    }

    private static void Merge(List<HashSet<string>> groups, HashSet<string> incoming)
    {
        int last = groups.Count - 1;
        if (groups[last].Count == 0)
        {
            groups[last] = incoming;
            return;
        }

        var merged = new HashSet<string>();
        foreach (string left in groups[last])
        {
            foreach (string right in incoming)
                merged.Add(left + right);
        }
        groups[last] = merged;
    }
}
Was this solution helpful?

Related Problems