Back to all solutions

#1087 - Brace Expansion

Problem Description

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

/**
 * @param {string} s
 * @return {string[]}
 */
var expand = function(s) {
  const groups = [];
  let i = 0;

  while (i < s.length) {
    if (s[i] === '{') {
      const start = i + 1;
      while (s[i] !== '}') i++;
      const options = s.substring(start, i).split(',');
      groups.push(options);
      i++;
    } else {
      groups.push([s[i]]);
      i++;
    }
  }

  const result = [];

  backtrack(0, '');

  return result.sort();

  function backtrack(index, current) {
    if (index === groups.length) {
      result.push(current);
      return;
    }

    for (const option of groups[index]) {
      backtrack(index + 1, current + option);
    }
  }
};