- 魔法师2026-09-25
佬友们中秋节快乐！！
力扣 LeetCode
1096. 花括号展开 II - 力扣（LeetCode）
1096. 花括号展开 II - 如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。
花括号展开的表达式可以看作一个由 花括号、逗号 和 小写英文字母 组成的字符串，定义下面几条语法规则：
- 如果只给出单一的元素 x，那么表达式表示的字符串就只有 "x"。R(x) = {x}
- 例如，表达式 "a" 表示字符串 "a"。
- 而表达式 "w" 就表示字符串 "w"。
*...
思路
跟四则运算思路差不多，递归，根据优先级和符号依次运算。
花括号内，从左往右遍历。缓存
now存还没结束的内容。- 如果遇到
{，找到对应的}，然后递归它中间的内容，然后与当前缓存值连接。- 如果遇到
,，把缓存加到ans，重置当前缓存。- 否则将缓存中的值依次与当前字符连接。
- 遍历结束后，如果缓存中还有值，加入到
ans。代码```
class Solution {
private char[] chars;
public List<String> braceExpansionII(String expression) {
chars = expression.toCharArray();
Set<String> ans = dfs(0, chars.length - 1);
return ans.stream().sorted().toList();
}private HashSet<String> dfs(int left, int right) {
int idx = left;
HashSet<String> ans = new HashSet<>();
HashSet<String> now = new HashSet<>();
now.add("");
while (idx <= right) {
if (chars[idx] == '{') {
int l = ++idx;
int deep = 1;
while (idx <= right){
if (chars[idx] == '}') {
if (--deep == 0) {
idx++;
break;
}
} else if (chars[idx] == '{') {
deep++;
}
idx++;
}
HashSet<String> link = dfs(l, idx - 2);
HashSet<String> next = new HashSet<>();
for (String s : now) {
for (String s1 : link) {
next.add(s + s1);
}
}
now = next;
} else if (chars[idx] == ',') {
ans.addAll(now);
now.clear();
now.add("");
idx++;
} else {
HashSet<String> next = new HashSet<>();
for (String s : now) {
next.add(s + chars[idx]);
}
now = next;
idx++;
}
}
if (!now.isEmpty()) {
ans.addAll(now);
}
return ans;
}
}主楼 - SomeBottle2026-09-25
佬友中秋节快乐啊！中秋节竟然上强度了…这题算是学到了神奇的 BFS 做法。```
class Solution {
public:
vector<string> braceExpansionII(string expression) {
// 输入规模并不大
// 括号嵌套括号等同于展开，去重
// 比如 {c,d,{d,e}} = {c, d, e}
// 可以用 BFS 来剥离括号并和前面的字符组成对auto split=[&](string& str) -> vector<string> {
// 切分字符串
vector<string> rt;
int start=0;
int pos=0;
bool found=false;
while(pos<str.size()){
if(str[pos]==','){
found=true;
rt.emplace_back(str.substr(start,pos-start));
start=pos+1;
}
pos++;
}
// 无论有没有逗号，都要加入最后一段
rt.emplace_back(str.substr(start));
return rt;
};vector<string> res;
unordered_set<string> sSet; // 去重后所有的字符串
queue<string> q; // 队列
q.emplace(expression);
while(!q.empty()){
string curr=q.front();
q.pop();
// 从左往右找到第一个右括号，肯定至少在这一块是最深的一个括号
int rightPos=-1;
for(int i=0;i<curr.size();i++){
if(curr[i]=='}'){
rightPos=i;
break;
}
}
if(rightPos==-1){
// 没有找到右括号，按剩下逗号拆分加入集合
for(string spStr:split(curr)){
sSet.insert(spStr);
}
continue;
}
// 如果找到了首个右括号，往左找对应的左括号
int leftPos=-1;
for(int i=rightPos;i>=0;i--){
if(curr[i]=='{'){
leftPos=i;
break;
}
}
// 比如 {c,d,{d,e}} 首次找到的就是 {d,e}, 逗号切分为 d,e
// 嵌套似乎也能展开处理，这里展开成 {c,d,d} 和 {c,d,e}
// 逗号切分后为 c, d, d, c, d, e
// 去重后就是 c, d, e// 又比如 {c,d,a{d,e}}，首次逗号切分为 d,e
// 展开的话就是 {c, d, ad} 和 {c, d, ae}
// 也就是说如果按嵌套展开的思路来做，然后去重就很自然了
string left=curr.substr(0,leftPos); // 拆出左括号左边的内容
string mid=curr.substr(leftPos+1,rightPos-leftPos-1); // 右括号和左括号之间的内容
string right=curr.substr(rightPos+1); // 右括号右边的内容
// 按逗号切开 mid
for(string spStr:split(mid)){
// 嵌套展开处理，每个切割出来的字符串拼接上左右两侧后再放回队列
q.emplace(left+spStr+right);
}
};
// 把 sSet 中的元素全部拿出来
for(string s:sSet){
res.emplace_back(s);
}
sort(res.begin(),res.end());
return res;
}
};