LC: 1087. Brace Expansion - spiralgo/algorithms GitHub Wiki

1087. Brace Expansion

The Essence:

The characters within a brace are concatenated with all the possible brace expansions to their, which itself might contain braces with combinations of their own. Thus, the brace expansion has a recursive structure.

For example: expand({a, b}e{c, d}) = {a, b} + expand(e{c, d})

Details: The recursion can be used in two ways:

1. The problem solver can choose to DFS the entire right string for each letters in the brace.
2. The problem solver can expand the right side, and concatenate it with all the characters in the brace.

The concatenation operation can be sped up using the build in the string building classes of programming languages.