05 August 2008
类似shell编程的大括号分层次展开，相同层次的大括号里的元素并行组成字符串，返回组成的字符串总数
DFS - 主要思路分成三种情况 空字符串”“，直接返回空集合 包含平级部分的，如{a},{b}这种形式，求出平级的左右部分的结果分别加入结果 不包含平级部分的，如a{b}{c}这种形式，先将第一对括号前的部分当作前缀，再求剥掉第一对括号的结果和第一对括号后面部分的结果，并将三者拼接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public List<String> braceExpansionII(String expression) {
return expansion(expression).stream().sorted().collect(Collectors.toList());
}
public Set<String> expansion(String expression) {
Set<String> result = new HashSet<>();
//空串返回空结果
if ("".equals(expression)) {
return result;
} else if (!expression.contains("{")) {
//不含{}，那么直接分割即可
return Arrays.stream(expression.split(",")).collect(Collectors.toSet());
} else {
//pairStart, pairEnd分另表示第一个完整的{}的位置
int pair = 0, pairStart = -1, pairEnd = -1;
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) == '{') {
if (pairStart == -1) {
pairStart = i;
}
pair++;
} else if (expression.charAt(i) == '}') {
pair--;
}
if (pair == 0) {
if (pairStart != - 1 && pairEnd == -1) {
pairEnd = i;
}
//pair==0，即不在某个{}中间，那么可以将表达式分成两段
if (expression.charAt(i) == ',') {
result.addAll(expansion(expression.substring(0, i)));
result.addAll(expansion(expression.substring(i + 1)));
return result;
}
}
}
//现在剩下的只会是{a{b}{c}} a{b}c {}{}这种形式的了
String prefix = "";
//括号起点不为0，说明是a{b}c这种形式
if (pairStart != 0) {
prefix = expression.substring(0, pairStart);
}
//剥掉第一个的最外层括号
Set<String> left = expansion(expression.substring(pairStart + 1, pairEnd));
//求出第一个完整{}后部分
Set<String> right = expansion(expression.substring(pairEnd + 1));
//为了方便计算加入空串
if (left.isEmpty()) {
left.add("");
}
if (right.isEmpty()) {
right.add("");
}
//拼接
for (String l: left) {
for (String r: right) {
result.add(prefix + l + r);
}
}
}
return result;
}
}
BFS - 按照第一个大括号里面的字符来BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public List<String> braceExpansionII(String expression) {
Queue<String> queue = new LinkedList<>();
queue.add(expression);
Set<String> res = new HashSet<>();
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
// 拿到需要处理的表达式
String exp = queue.poll();
// 如果表达式中没有 {，则将这个表达式加入结果中
if (exp.indexOf("{") == -1) {
res.add(exp);
continue;
}
// 找到表达式中第一对 {}
int i = 0;
int left = 0;
int right = 0;
while (exp.charAt(i) != '}') {
if (exp.charAt(i) == '{') left = i;
i++;
}
right = i;
// 拿到第一对括号中的前面部分 (不包括 {)
String before = exp.substring(0, left);
// 拿到第一对括号中的后面部分 (不包括 })
String after = exp.substring(right + 1);
// 按照 , 分割第一对括号中的元素 (不包括 {})
String[] strs = exp.substring(left + 1, right).split(",");
// 将 before 、 strs 中的每个元素以及 after 拼接成字符串放入到队列中，方便后面处理
for (String str : strs) {
sb.setLength(0);
queue.add(sb.append(before).append(str).append(after).toString());
}
}
// 结果处理
List<String> ans = new ArrayList<>(res);
Collections.sort(ans);
return ans;
}
}