LeetCode 1087 - Brace Expansion

In this problem, we are given a string that represents multiple possible words. Each position in the word may contain either a single fixed character or a set of alternative characters enclosed in curly braces.

leetcodemediumstringbacktrackingstackbreadth-first-searchsorting

LeetCode Problem 1087

Difficulty: 🟡 Medium
Topics: String, Backtracking, Stack, Breadth-First Search, Sorting

Solution

Problem Understanding

In this problem, we are given a string that represents multiple possible words. Each position in the word may contain either a single fixed character or a set of alternative characters enclosed in curly braces.

For example:

a{b,c}d

means:

  • The first character is always 'a'
  • The second character can be either 'b' or 'c'
  • The third character is always 'd'

So the valid generated words are:

["abd", "acd"]

The task is to generate every possible word that can be formed by choosing one option from each position, then return the results sorted in lexicographical order.

The input format has several guarantees that simplify the problem:

  • There are no nested braces.
  • Every brace group contains distinct lowercase letters.
  • The string is always valid.
  • The maximum length is only 50 characters.

These constraints tell us that parsing the string is relatively straightforward. Since there are no nested braces, we never need recursive parsing logic or stack-based expression evaluation. We only need to identify whether the current position is:

  • a single character, or
  • a comma-separated option group.

The major challenge is generating all combinations correctly and efficiently.

An important observation is that the total number of generated strings can grow exponentially. For example:

{a,b,c}{d,e,f}{g,h,i}

already produces:

3 × 3 × 3 = 27

results.

This means any correct solution must ultimately spend time proportional to the number of generated words.

Some important edge cases include:

  • Strings with no braces at all, such as "abcd"
  • A brace group appearing at the beginning or end
  • Multiple consecutive brace groups
  • Single-option groups like "{a}", even though uncommon
  • Lexicographical ordering requirements

The problem guarantees valid syntax, so we do not need to handle malformed brace expressions.

Approaches

Brute Force Approach

The brute force idea is to recursively try every possible interpretation directly from the raw string without preprocessing.

At each character:

  • If the character is a normal letter, append it to the current string.
  • If the character is '{', scan forward until '}', extract all options, and recursively branch for each one.

This works because every valid word corresponds to exactly one sequence of choices from each position.

However, this approach repeatedly scans portions of the string during recursion. Every recursive branch may need to search for closing braces and repeatedly parse comma-separated options. That introduces unnecessary repeated work.

Although the constraints are small enough that this would still pass, it is not the cleanest or most efficient design.

Optimal Approach

The key insight is that the problem naturally separates into two phases:

  1. Parse the input into groups of character choices
  2. Generate all combinations using backtracking

For example:

"{a,b}c{d,e}"

can first be transformed into:

[
    ['a', 'b'],
    ['c'],
    ['d', 'e']
]

Once we have this structure, the problem becomes a classic Cartesian product generation problem.

Backtracking is ideal here because:

  • Each position contributes one character
  • We build strings incrementally
  • Every recursive level corresponds to one character position
  • We explore every valid combination exactly once

Sorting becomes easy if we sort each option group before backtracking. Since recursion explores choices in order, the generated results automatically appear lexicographically sorted.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(N × K) O(K) Repeatedly reparses sections of the string during recursion
Optimal O(N + K) O(K) Parses once, then generates combinations efficiently

Where:

  • N = length of input string
  • K = total size of all generated output strings

Since output generation itself is unavoidable, K dominates the complexity.

Algorithm Walkthrough

Step 1: Parse the String into Option Groups

We iterate through the input string from left to right.

If the current character is a lowercase letter:

  • Create a single-option group containing that character.

If the current character is '{':

  • Continue scanning until '}'
  • Split the contents by commas
  • Sort the extracted options
  • Store them as one group

For example:

"{a,b}c{d,e}"

becomes:

[
    ['a', 'b'],
    ['c'],
    ['d', 'e']
]

This preprocessing step makes the generation phase much simpler.

Step 2: Use Backtracking to Build Words

We recursively process one group at a time.

At recursion level i:

  • Choose one character from groups[i]
  • Append it to the current partial word
  • Recurse to the next group
  • Remove the character afterward to backtrack

This explores every possible combination.

Step 3: Store Complete Words

When the recursion depth equals the number of groups:

  • We have selected one character from every position
  • Join the accumulated characters into a complete word
  • Add it to the result list

Step 4: Return the Result

Because groups and options were processed in sorted order, the generated results are already lexicographically sorted.

No additional sorting step is required.

Why it works

The algorithm works because every generated word corresponds to choosing exactly one option from each parsed group.

The recursion systematically explores all such choices without duplication:

  • Each recursive level represents one position in the final word.
  • Every valid option for that position is explored.
  • Backtracking restores state correctly before trying the next option.

Since all combinations are explored exactly once, and choices are processed in sorted order, the algorithm generates every valid word in lexicographical order.

Python Solution

from typing import List

class Solution:
    def expand(self, s: str) -> List[str]:
        groups = []
        i = 0

        # Parse the input into groups
        while i < len(s):
            if s[i] == '{':
                j = i

                while s[j] != '}':
                    j += 1

                options = s[i + 1:j].split(',')
                options.sort()

                groups.append(options)
                i = j + 1
            else:
                groups.append([s[i]])
                i += 1

        result = []
        path = []

        # Backtracking
        def backtrack(index: int) -> None:
            if index == len(groups):
                result.append(''.join(path))
                return

            for char in groups[index]:
                path.append(char)
                backtrack(index + 1)
                path.pop()

        backtrack(0)

        return result

The implementation begins by parsing the string into a list of groups. Each group contains all valid characters for one position in the final word.

For brace expressions, we scan until the closing brace, split by commas, sort the options, and store them together. For normal letters, we simply create a one-element group.

After parsing, we use a recursive backtracking function.

The path list stores the current partially constructed word. At each recursion level, we iterate through all possible characters for the current position.

When we reach the end of all groups, we join the characters in path into a string and append it to the result.

The append and pop operations implement classic backtracking state management. Each recursive call temporarily adds a character, explores deeper combinations, then restores the previous state.

Because all options are sorted before recursion starts, the generated results naturally appear in lexicographical order.

Go Solution

package main

import (
	"sort"
	"strings"
)

func expand(s string) []string {
	var groups [][]string

	// Parse the input
	for i := 0; i < len(s); {
		if s[i] == '{' {
			j := i

			for s[j] != '}' {
				j++
			}

			options := strings.Split(s[i+1:j], ",")
			sort.Strings(options)

			groups = append(groups, options)
			i = j + 1
		} else {
			groups = append(groups, []string{string(s[i])})
			i++
		}
	}

	var result []string
	var path []string

	var backtrack func(int)

	backtrack = func(index int) {
		if index == len(groups) {
			result = append(result, strings.Join(path, ""))
			return
		}

		for _, ch := range groups[index] {
			path = append(path, ch)
			backtrack(index + 1)
			path = path[:len(path)-1]
		}
	}

	backtrack(0)

	return result
}

The Go implementation follows the same overall algorithm as the Python version.

One notable difference is that Go strings are immutable, so the current word is stored as a slice of strings called path. When a full word is constructed, strings.Join combines the characters.

Backtracking state restoration uses slice truncation:

path = path[:len(path)-1]

This efficiently removes the last appended character.

The parser uses strings.Split to extract brace options and sort.Strings to maintain lexicographical order.

Worked Examples

Example 1

Input:

"{a,b}c{d,e}f"

Parsing Phase

Position Parsed Group
{a,b} ['a', 'b']
c ['c']
{d,e} ['d', 'e']
f ['f']

Final groups:

[
    ['a', 'b'],
    ['c'],
    ['d', 'e'],
    ['f']
]

Backtracking Trace

Step Path Action
1 ['a'] choose 'a'
2 ['a', 'c'] choose 'c'
3 ['a', 'c', 'd'] choose 'd'
4 ['a', 'c', 'd', 'f'] choose 'f'
5 "acdf" add result
6 backtrack remove 'f'
7 ['a', 'c', 'e', 'f'] choose 'e', then 'f'
8 "acef" add result
9 continue with 'b' branch repeat process

Final output:

["acdf", "acef", "bcdf", "bcef"]

Example 2

Input:

"abcd"

Parsing Phase

Character Parsed Group
a ['a']
b ['b']
c ['c']
d ['d']

Groups:

[
    ['a'],
    ['b'],
    ['c'],
    ['d']
]

Since every group has only one option, recursion follows exactly one path:

a -> b -> c -> d

Final output:

["abcd"]

Complexity Analysis

Measure Complexity Explanation
Time O(N + K) Parsing takes O(N), generating all output strings takes O(K)
Space O(K) Output storage dominates memory usage

Where:

  • N is the input string length
  • K is the total number of characters across all generated strings

The recursive call stack depth is at most the number of character positions, which is bounded by the input length. Since every valid output must be stored, the result list dominates space complexity.

Test Cases

from typing import List

class Solution:
    def expand(self, s: str) -> List[str]:
        groups = []
        i = 0

        while i < len(s):
            if s[i] == '{':
                j = i

                while s[j] != '}':
                    j += 1

                options = s[i + 1:j].split(',')
                options.sort()

                groups.append(options)
                i = j + 1
            else:
                groups.append([s[i]])
                i += 1

        result = []
        path = []

        def backtrack(index: int) -> None:
            if index == len(groups):
                result.append(''.join(path))
                return

            for ch in groups[index]:
                path.append(ch)
                backtrack(index + 1)
                path.pop()

        backtrack(0)

        return result

sol = Solution()

assert sol.expand("{a,b}c{d,e}f") == [
    "acdf",
    "acef",
    "bcdf",
    "bcef",
]  # provided example

assert sol.expand("abcd") == [
    "abcd"
]  # no brace groups

assert sol.expand("{a,b,c}") == [
    "a",
    "b",
    "c",
]  # single brace group

assert sol.expand("a{b,c,d}") == [
    "ab",
    "ac",
    "ad",
]  # brace group at end

assert sol.expand("{a,b}z") == [
    "az",
    "bz",
]  # brace group at beginning

assert sol.expand("{a,b}{c,d}") == [
    "ac",
    "ad",
    "bc",
    "bd",
]  # multiple consecutive groups

assert sol.expand("x") == [
    "x"
]  # smallest possible input

assert sol.expand("{c,b,a}") == [
    "a",
    "b",
    "c",
]  # verifies lexicographical sorting

assert sol.expand("{a,b}c") == [
    "ac",
    "bc",
]  # mixed fixed and variable characters

Test Summary

Test Why
"{a,b}c{d,e}f" Validates standard mixed expansion
"abcd" Verifies no-brace handling
"{a,b,c}" Tests single brace group
"a{b,c,d}" Tests brace group at end
"{a,b}z" Tests brace group at beginning
"{a,b}{c,d}" Tests consecutive variable groups
"x" Smallest valid input
"{c,b,a}" Verifies sorting behavior
"{a,b}c" Tests mixed fixed and variable positions

Edge Cases

Input Without Any Braces

A common source of bugs is assuming every input contains brace expressions. For inputs like:

"abcd"

the algorithm must still work correctly.

The parser handles this naturally by treating each character as a single-option group:

[['a'], ['b'], ['c'], ['d']]

The backtracking phase then produces exactly one result.

Consecutive Brace Groups

Inputs such as:

"{a,b}{c,d}"

can expose indexing or recursion mistakes because there are no fixed characters separating groups.

The parser correctly processes each brace block independently, producing:

[['a', 'b'], ['c', 'd']]

Backtracking then explores all Cartesian product combinations.

Lexicographical Ordering

The problem requires sorted output, which can be overlooked if brace options are processed in their original order.

For example:

"{c,b,a}"

must produce:

["a", "b", "c"]

The implementation explicitly sorts every brace group's options before recursion begins. Since backtracking traverses choices in sorted order, the final results are automatically lexicographically ordered without requiring a separate sort step afterward.