Brace Expansion

Problem

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.

Examples

Example 1:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: s = "abcd"
Output: ["abcd"]

Solution

Method 1 - Backtracking

The problem aims to generate all possible combination strings. Upon encountering a {, combinations are formed using the given options, then the process continues from the character following }. For regular letters, the next character in the string is processed directly. Finally, the resulting combinations are sorted in ascending lexicographical order.

This problem is close to [Letter Combinations of a Phone Number](letter-combinations-of-a-phone-number)

Here is the approach:

1. Parse the given string s using a loop:
   • If a character is not enclosed in {}, treat it as a single option (e.g., 'a' becomes ['a']).
   • If a character is enclosed in {}, extract all options (e.g., "{b,c}" becomes ['b', 'c']).
2. Use backtracking to generate all possible combinations of words:
   • Start at the first position and choose an option for each component.
   • Recursively combine options from subsequent components.
3. After generating all possible combinations, sort the resultant list of words lexicographically.

Approach 1 - With Treeset

//idea is merging any closing two parts
//using dfs recursion is the approach
//there are two cases, single char
//or {a, b}, using set

//O(n^2) time complexity, at most O(n) combination
//each take O(n) time.
public String[] expand(String S) {
	TreeSet<String> set = new TreeSet<>();
	if (S.length() <= 1) {
		return new String[]{S};
	}

	int idx = 0;
	if (S.charAt(idx) == '{') {
		while (S.charAt(idx) != '}') {
			idx++;
		}
		String[] str1 = S.substring(1, idx).split(",");
		String[] str2 = expand(S.substring(idx+1));
		for (String s1: str1) {
			for (String s2: str2) {
				set.add(s1 + s2);
			}
		}
	} else { //single char
		String[] str3 = expand(S.substring(idx+1));
		for (String s3: str3) {
			set.add(S.charAt(idx) + s3);
		}
	}
	return set.toArray(new String[0]);
}

Without Treeset

public String[] expand(String S) {
	if (S == null || S.length() == 0) {
		return new String[0];
	}

	List<String> res = new ArrayList<String> ();
	dfs(S, 0, new StringBuilder(), res);
	Collections.sort(res);
	return res.toArray(new String[0]);
}

private void dfs(String s, int i, StringBuilder sb, List<String> res) {
	if (i >= s.length()) {
		res.add(sb.toString());
		return;
	}

	if (s.charAt(i) == '{') {
		int j = i + 1;
		while (j<s.length() && s.charAt(j) != '}') {
			j++;

		}
		String[] candidates = s.substring(i + 1, j).split(",");
		for (String candidate: candidates) {
			sb.append(candidate);
			dfs(s, j + 1, sb, res);
			sb.deleteCharAt(sb.length() - 1);
		}
	} else {
		sb.append(s.charAt(i));
		dfs(s, i + 1, sb, res);
		sb.deleteCharAt(sb.length() - 1);
	}
}

Complexity

• ⏰ Time complexity: O(n + k^m + p log(p)) Parsing the string requires one scan: O(n), where n is the length of the string. Backtracking generates all combinations, which takes O(k^m), where m is the number of components (letters or sets of options) and k is the maximum number of options per component. Sorting the results requires O(p log(p)), where p is the number of generated words. Overall: O(n + k^m + p log(p)).
• 🧺 Space complexity: O(m * k + p). The storage for options uses O(m * k). The recursive call stack uses up to O(m) additional memory, and the result list takes O(p) space.