Brace expansion

String Backtracking Stack Breadth-First Search Sorting

66.8% acceptance

Mar 31, 2026

664

You are given a string s representing a list of words. Each letter in the word has one or more options. If there is one option, the letter is represented as is. If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"]. For example, if s = "a{b,c}", the first character is always 'a', but the second character can be 'b' or 'c'. The original list is ["ab", "ac"]. Return all words that can be formed in this manner, sorted in lexicographical order.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn expand(s: String) -> Vec<String> {
    let mut groups: Vec<Vec<char>> = Vec::new();
    let chars: Vec<char> = s.chars().collect();
    let mut i = 0;
    while i < chars.len() {
      if chars[i] == '{' {
        let j = chars[i..].iter().position(|&c| c == '}').unwrap() + i;
        let mut group: Vec<char> = chars[i+1..j].iter().filter(|&&c| c != ',').cloned().collect();
        group.sort_unstable();
        groups.push(group);
        i = j + 1;
      } else {
        groups.push(vec![chars[i]]);
        i += 1;
      }
    }
    let mut result = vec![String::new()];
    for group in &groups {
      let mut next = Vec::new();
      for prefix in &result {
        for &c in group {
          next.push(format!("{}{}", prefix, c));
        }
      }
      result = next;
    }
    result.sort_unstable();
    result
  }
}