2019-11-26 11:05:10
问题描述：
问题求解：
经典的字符串扩展问题。
一般来说这种问题有两种解法，一个是采用stack，一个是采用recursive。事实证明，这种题目采用recursive在时间效率和程序易读性上要远远高于stack，请尽量采用recursive。
本题有个很好的讲解视频：https://www.youtube.com/watch?v=blXuT7DOMwU
public List<String> braceExpansionII(String expression) {
List<String> res = new ArrayList<>();
if (expression.length() <= 1) {
res.add(expression);
return res;
}
if (expression.charAt(0) == ‘{‘) {
int cnt = 0;
int idx = 0;
for (; idx < expression.length(); idx++) {
if (expression.charAt(idx) == ‘{‘) cnt += 1;
if (expression.charAt(idx) == ‘}‘) cnt -= 1;
if (cnt == 0) break;
}
List<String> strs = helper(expression.substring(1, idx));
HashSet<String> set = new HashSet<>();
for (String str : strs) {
List<String> tmp = braceExpansionII(str);
set.addAll(tmp);
}
List<String> rest = braceExpansionII(expression.substring(idx + 1));
for (String str1 : set) {
for (String str2 : rest) {
res.add(str1 + str2);
}
}
}
else {
String prev = expression.charAt(0) + "";
int idx = 0;
List<String> rest = braceExpansionII(expression.substring(1));
for (String s : rest) res.add(prev + s);
}
Collections.sort(res);
return res;
}
public List<String> helper(String s) {
List<String> res = new ArrayList<>();
int cnt = 0;
int i = 0;
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == ‘,‘) {
if (cnt == 0) {
res.add(s.substring(i, j));
i = j + 1;
}
}
else if (s.charAt(j) == ‘{‘) cnt += 1;
else if (s.charAt(j) == ‘}‘) cnt -= 1;
}
res.add(s.substring(i));
return res;
}
原文：https://www.cnblogs.com/hyserendipity/p/11934167.html