Comment on page

1087.Brace-Expansion

1087. Brace Expansion

题目地址

题目描述

A string S represents a list of words.
​
Each letter in the word has 1 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, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].
​
Return all words that can be formed in this manner, in lexicographical order.
​
Example 1:
Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]
​
Example 2:
Input: "abcd"
Output: ["abcd"]
​
Note:
1 <= S.length <= 50
There are no nested curly brackets.
All characters inside a pair of consecutive opening and ending curly brackets are different.

代码

Approach #1 DFS

Time: O(N) && Space: O(N)
class Solution {
public String[] expand(String S) {
TreeSet<String> set = new TreeSet<>();
if (S.length() == 0) {
return new String[]{""};
} else if (S.length() == 1) {
return new String[]{S};
}
​
if (S.charAt(0) == '{') {
int i = 0;
while (S.charAt(i) != '}') {
i++;
}
String sub = S.substring(1, i);
String[] subs = sub.split(",");
String[] strs = expand(S.substring(i + 1)); // dfs
for (int j = 0; j < subs.length; j++) {
for (String str: strs) {
set.add(subs[j] + str);
}
}
} else {
String[] strs = expand(S.substring(1));
for (String str: strs) {
set.add(S.charAt(0) + str);
}
}
return set.toArray(new String[0]);
}
}

#2 Without TreeSet

class Solution {
public String[] expand(String S) {
int n = S.length();
if (n == 0) {
return new String[]{""};
}
if (n == 1) {
return new String[]{S};
}
​
List<String> res = new ArrayList<>();
if (S.charAt(0) == '{') {
int count = 0;
int i = 0;
while (i < S.length()) {
if (S.charAt(i) == '}') {
break;
}
i++;
}
String[] l = S.substring(1, i).split(",");
String[] r = expand(S.substring(i + 1));
for (String ll: l) {
for (String rr: r) {
res.add(ll + rr);
}
}
} else {
String[] r = expand(S.substring(1));
for (String rr: r) {
res.add(S.charAt(0) + rr);
}
}
Collections.sort(res);
return res.toArray(new String[0]);
}
}