企业官网建设流程全解析

【LetMeFly】1096.花括号展开 II：一个一百行的解题方法（DFS）

力扣题目链接：https://leetcode.cn/problems/brace-expansion-ii/

如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。

花括号展开的表达式可以看作一个由花括号、逗号和小写英文字母组成的字符串，定义下面几条语法规则：

• 如果只给出单一的元素x，那么表达式表示的字符串就只有"x"。R(x) = {x}

  <ul> <li>例如，表达式 <code>"a"</code> 表示字符串 <code>"a"</code>。</li> <li>而表达式 <code>"w"</code> 就表示字符串 <code>"w"</code>。</li> </ul> </li> <li>当两个或多个表达式并列，以逗号分隔，我们取这些表达式中元素的并集。<code>R({e_1,e_2,...}) = R(e_1)&nbsp;∪ R(e_2)&nbsp;∪ ...</code> <ul> <li>例如，表达式 <code>"{a,b,c}"</code> 表示字符串&nbsp;<code>"a","b","c"</code>。</li> <li>而表达式 <code>"{{a,b},{b,c}}"</code> 也可以表示字符串&nbsp;<code>"a","b","c"</code>。</li> </ul> </li> <li>要是两个或多个表达式相接，中间没有隔开时，我们从这些表达式中各取一个元素依次连接形成字符串。<code>R(e_1 + e_2) = {a + b for (a, b) in&nbsp;R(e_1)&nbsp;× R(e_2)}</code> <ul> <li>例如，表达式 <code>"{a,b}{c,d}"</code> 表示字符串&nbsp;<code>"ac","ad","bc","bd"</code>。</li> </ul> </li> <li>表达式之间允许嵌套，单一元素与表达式的连接也是允许的。 <ul> <li>例如，表达式 <code>"a{b,c,d}"</code> 表示字符串&nbsp;<code>"ab","ac","ad"​​​​​​</code>。</li> <li>例如，表达式 <code>"a{b,c}{d,e}f{g,h}"</code> 可以表示字符串&nbsp;<code>"abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"</code>。</li> </ul> </li>

给出表示基于给定语法规则的表达式expression，返回它所表示的所有字符串组成的有序列表。

假如你希望以「集合」的概念了解此题，也可以通过点击 “显示英文描述” 获取详情。

示例 1：

输入：expression = "{a,b}{c,{d,e}}"输出：["ac","ad","ae","bc","bd","be"]

示例 2：

输入：expression = "{{a,z},a{b,c},{ab,z}}"输出：["a","ab","ac","z"]解释：输出中不应出现重复的组合结果。

提示：

• 1 <= expression.length <= 60
• expression[i]由'{'，'}'，','或小写英文字母组成
• 给出的表达式expression用以表示一组基于题目描述中语法构造的字符串

解题方法：深度优先搜索

解题思路

这种题最容易想到的就是递归。怎么递归？

1. 如果最外层是加法运算，如<A,B,C>，则返回dfs(A) + dfs(B) + dfs(C)。例如：

   • {a,b},c：dfs({a,b}) + dfs(c)
   • a,b,c：dfs(a) + dfs(b) + dfs(c)
   • a,{b,c}：dfs(a) + dfs({b,c})
   • {a,b{c}},{d,ef}：dfs({a,b{c}}) + dfs({d,ef})

   仅限于最外层是加法的运算。

2. 否则（说明可能有两种情况，要么最外层是乘法运算，要么就只有一个“运算单元”）如果最外层是乘法运算，如ABC，则返回dfs(A) * dfs(B) * dfs(C)。例如：

   • {a,b}{c,d}：dfs({a,b}) * dfs({c,d})
   • a{b,c}：dfs(a) * dfs({b,c})
   • {a,b}c：dfs({a,b}) * dfs(c)
   • {a}b：dfs({a}) * dfs(b)
   • {a}：dfs({a})。注意这种被大括号包括的特殊情况

3. 否则（说明只有一个单一的“运算单元”）。如果字符串第一个字符是{，则再次递归大括号中间的字符串；否则说明该字符串是不含{也不含,的单一字符串，直接返回该字符串。例如：

   • {a}：dfs(a)
   • {a,bc}：dfs(a,bc)
   • a：a。不再递归
   • ab：ab。不再递归

以上。

其实相当于递归终止条件是不含{也不含,的单一字符串。

解题细节

怎么判断最外层是否是加法运算？

使用一个变量layer记录当前的括号层数，初始值是0。遇到{则layer++，遇到}则layer--。当遇到,时，如果此时layer==0，说明这个,是最外层的加法运算符，视为最外层为加法运算。

同时我们也可以返回所有最外层,的下标。

怎么判断最外层是否是乘法运算？

（如果前面判断是否是加法运算时候返回了一个空数组，说明没有最外层的逗号，才会执行该判断最外层是否是乘法运算的算法）。

同样使用一个变量layer记录当前的括号层数，初始值是0。遇到{则layer++，遇到}则layer--。当遇到一个字符时，如果此时layer==0，并且该字符的前一个字符是}或者该字符是{，说明不只有一个“运算单元”，视为最外层为乘法运算。

同时我们也可以返回所有（除了起始下标0外的）最外层“运算单元”起始位置的下标，例如{a,b}{c,d}e相当于三个运算单元{a,b}、{c,d}和e相乘，返回下标[5, 10]。

如果返回下标为空数组，说明只有一个“运算单元”，依据第一个字符是否为{来决定是否需要继续递归；否则说明该字符串总体上是不只一个运算单元的相乘，递归每个运算单元并相乘。

时空复杂度(我不会算)

• 时间复杂度O ( u n k n o w n ) O(unknown)O(unknown)
• 空间复杂度O ( u n k n o w n ) O(unknown)O(unknown)

AC代码

C++

/* * @LastEditTime: 2026-09-26 11:31:38 */// struct Res : unordered_set<string> {// Res() : unordered_set<string>{""} {}// };typedefunordered_set<string>Res;Resoperator*(constRes&a,constRes&b){Res res;for(conststring&s1:a){for(conststring&s2:b){res.insert(s1+s2);}}returnres;}Resoperator+=(Res&a,constRes&b){a.insert(b.begin(),b.end());returna;}typedefvector<int>Idx;classSolution{private:// 最外层是加法运算IdxgetAdd(string_view s){Idx idxs;intlayer=0;for(inti=0,n=s.size();i<n;i++){if(s[i]=='{'){layer++;}elseif(s[i]=='}'){layer--;}elseif(s[i]==','&&!layer){idxs.push_back(i);}}returnidxs;}IdxgetMul(string_view s){Idx idxs;intlayer=0;for(inti=0,n=s.size();i<n;i++){if(!layer&&i&&(s[i-1]=='}'||s[i]=='{')){idxs.push_back(i);}if(s[i]=='{'){layer++;}elseif(s[i]=='}'){layer--;}}returnidxs;}Resdfs(string_view s){Res res;Idx idxs=getAdd(s);if(idxs.size()){// 最外层是加法运算idxs.push_back(s.size());intlast_idx=-1;for(intidx:idxs){res+=dfs(s.substr(last_idx+1,idx-last_idx-1));last_idx=idx;}returnres;}// 最外层是乘法运算(或单个字符串)idxs=getMul(s);if(idxs.empty()&&s.size()&&s[0]!='{'){// 没有括号，那就是单个字符串res.insert(string(s));returnres;}if(idxs.empty()){// 只有最外层一个大括号，如 {a,b}returndfs(s.substr(1,s.size()-2));}idxs.push_back(s.size());intlast_idx=0;res.insert("");for(intidx:idxs){res=res*dfs(s.substr(last_idx,idx-last_idx));last_idx=idx;}returnres;}public:vector<string>braceExpansionII(string expression){Res res=dfs(expression);vector<string>ans(res.begin(),res.end());sort(ans.begin(),ans.end());returnans;}};/* c{a{b}}d {{a,z},a{b,c},{ab,z}} {ab,c}{d},{e} a{b,c} {a,b}c {a}b {a} d,a{b,c} */#ifdef_DEBUGintmain(){string s;while(cin>>s){Solution sol;debug(sol.braceExpansionII(s));}return0;}#endif

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源