Brace Expansion

medium backtracking dfs string

Problem

You are given a string s where every position is either a single lowercase letter or a group of comma-separated letters enclosed in curly braces like {a,b,c}. Generate all words that can be formed by picking exactly one letter from each position, in left-to-right order, and return them sorted lexicographically.

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

Output["acd", "ace", "bcd", "bce"]

Groups are [a,b], [c], [d,e]. Choosing one from each gives 2 × 1 × 2 = 4 words, sorted.

s (e.g. {a,b}c{d,e})

def expand(s):
    groups = []
    i = 0
    while i < len(s):
        if s[i] == '{':
            j = s.index('}', i)
            groups.append(sorted(s[i + 1:j].split(',')))
            i = j + 1
        else:
            groups.append([s[i]])
            i += 1
    res = []
    def dfs(k, path):
        if k == len(groups):
            res.append(''.join(path))
            return
        for ch in groups[k]:
            path.append(ch)
            dfs(k + 1, path)
            path.pop()
    dfs(0, [])
    return res

function expand(s) {
  const groups = [];
  let i = 0;
  while (i < s.length) {
    if (s[i] === '{') {
      const j = s.indexOf('}', i);
      groups.push(s.slice(i + 1, j).split(',').sort());
      i = j + 1;
    } else {
      groups.push([s[i]]);
      i += 1;
    }
  }
  const res = [];
  function dfs(k, path) {
    if (k === groups.length) {
      res.push(path.join(''));
      return;
    }
    for (const ch of groups[k]) {
      path.push(ch);
      dfs(k + 1, path);
      path.pop();
    }
  }
  dfs(0, []);
  return res;
}

class Solution {
    public String[] expand(String s) {
        List<List<String>> groups = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '{') {
                int j = s.indexOf('}', i);
                String[] parts = s.substring(i + 1, j).split(",");
                Arrays.sort(parts);
                groups.add(Arrays.asList(parts));
                i = j + 1;
            } else {
                groups.add(List.of(String.valueOf(s.charAt(i))));
                i += 1;
            }
        }
        List<String> res = new ArrayList<>();
        dfs(groups, 0, new StringBuilder(), res);
        return res.toArray(new String[0]);
    }
    private void dfs(List<List<String>> g, int k, StringBuilder path, List<String> res) {
        if (k == g.size()) { res.add(path.toString()); return; }
        for (String ch : g.get(k)) {
            path.append(ch);
            dfs(g, k + 1, path, res);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

vector<string> expand(string s) {
    vector<vector<string>> groups;
    int i = 0;
    while (i < (int)s.size()) {
        if (s[i] == '{') {
            int j = s.find('}', i);
            vector<string> g;
            string cur;
            for (int k = i + 1; k < j; k++) {
                if (s[k] == ',') { g.push_back(cur); cur.clear(); }
                else cur += s[k];
            }
            g.push_back(cur);
            sort(g.begin(), g.end());
            groups.push_back(g);
            i = j + 1;
        } else {
            groups.push_back({string(1, s[i])});
            i += 1;
        }
    }
    vector<string> res;
    string path;
    function<void(int)> dfs = [&](int k) {
        if (k == (int)groups.size()) { res.push_back(path); return; }
        for (auto& ch : groups[k]) {
            path += ch;
            dfs(k + 1);
            path.pop_back();
        }
    };
    dfs(0);
    return res;
}

Explanation

The problem is really two steps: first parse the string into a list of choice groups, then combine by picking one letter from each group. The result is every possible word.

Parsing walks through s left to right. When it sees { it reads up to the matching }, splits the inside on commas, sorts those letters, and stores them as one group. A plain letter outside braces becomes a group of just that one letter. Sorting here is the trick that makes the final list come out in lexicographic order.

The combine step is a depth-first search. dfs(k, path) means "I have already chosen letters for groups before k, stored in path." For group k it tries each letter, recurses to the next group, then removes it (backtracks) to try the next option. When k reaches the end, path is a full word and gets joined and saved.

Example: "{a,b}c{d,e}" parses to groups [a,b], [c], [d,e]. The DFS picks a, then c, then d → "acd"; backtracks to pick e → "ace"; and so on, giving ["acd","ace","bcd","bce"].

Because each group is already sorted and we explore them in order, the words naturally appear sorted without any extra sorting at the end.

Time: O(n + k·∏|gᵢ|) Space: O(n + ∏|gᵢ|)