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

【LetMeFly】1096.花括号展开 II一个一百行的解题方法DFS力扣题目链接https://leetcode.cn/problems/brace-expansion-ii/如果你熟悉 Shell 编程那么一定了解过花括号展开它可以用来生成任意字符串。花括号展开的表达式可以看作一个由花括号、逗号和小写英文字母组成的字符串定义下面几条语法规则如果只给出单一的元素x那么表达式表示的字符串就只有x。R(x) {x}ul li例如表达式 codea/code 表示字符串 codea/code。/li li而表达式 codew/code 就表示字符串 codew/code。/li /ul /li li当两个或多个表达式并列以逗号分隔我们取这些表达式中元素的并集。codeR({e_1,e_2,...}) R(e_1)nbsp;∪ R(e_2)nbsp;∪ .../code ul li例如表达式 code{a,b,c}/code 表示字符串nbsp;codea,b,c/code。/li li而表达式 code{{a,b},{b,c}}/code 也可以表示字符串nbsp;codea,b,c/code。/li /ul /li li要是两个或多个表达式相接中间没有隔开时我们从这些表达式中各取一个元素依次连接形成字符串。codeR(e_1 e_2) {a b for (a, b) innbsp;R(e_1)nbsp;× R(e_2)}/code ul li例如表达式 code{a,b}{c,d}/code 表示字符串nbsp;codeac,ad,bc,bd/code。/li /ul /li li表达式之间允许嵌套单一元素与表达式的连接也是允许的。 ul li例如表达式 codea{b,c,d}/code 表示字符串nbsp;codeab,ac,ad​​​​​​/code。/li li例如表达式 codea{b,c}{d,e}f{g,h}/code 可以表示字符串nbsp;codeabdfg, 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 60expression[i]由{},或小写英文字母组成给出的表达式expression用以表示一组基于题目描述中语法构造的字符串解题方法深度优先搜索解题思路这种题最容易想到的就是递归。怎么递归如果最外层是加法运算如A,B,C则返回dfs(A) dfs(B) dfs(C)。例如{a,b},cdfs({a,b}) dfs(c)a,b,cdfs(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})仅限于最外层是加法的运算。否则说明可能有两种情况要么最外层是乘法运算要么就只有一个“运算单元”如果最外层是乘法运算如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}cdfs({a,b}) * dfs(c){a}bdfs({a}) * dfs(b){a}dfs({a})。注意这种被大括号包括的特殊情况否则说明只有一个单一的“运算单元”。如果字符串第一个字符是{则再次递归大括号中间的字符串否则说明该字符串是不含{也不含,的单一字符串直接返回该字符串。例如{a}dfs(a){a,bc}dfs(a,bc)aa。不再递归abab。不再递归以上。其实相当于递归终止条件是不含{也不含,的单一字符串。解题细节怎么判断最外层是否是加法运算使用一个变量layer记录当前的括号层数初始值是0。遇到{则layer遇到}则layer--。当遇到,时如果此时layer0说明这个,是最外层的加法运算符视为最外层为加法运算。同时我们也可以返回所有最外层,的下标。怎么判断最外层是否是乘法运算如果前面判断是否是加法运算时候返回了一个空数组说明没有最外层的逗号才会执行该判断最外层是否是乘法运算的算法。同样使用一个变量layer记录当前的括号层数初始值是0。遇到{则layer遇到}则layer--。当遇到一个字符时如果此时layer0并且该字符的前一个字符是}或者该字符是{说明不只有一个“运算单元”视为最外层为乘法运算。同时我们也可以返回所有除了起始下标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_setstring {// Res() : unordered_setstring{} {}// };typedefunordered_setstringRes;Resoperator*(constResa,constResb){Res res;for(conststrings1:a){for(conststrings2:b){res.insert(s1s2);}}returnres;}Resoperator(Resa,constResb){a.insert(b.begin(),b.end());returna;}typedefvectorintIdx;classSolution{private:// 最外层是加法运算IdxgetAdd(string_view s){Idx idxs;intlayer0;for(inti0,ns.size();in;i){if(s[i]{){layer;}elseif(s[i]}){layer--;}elseif(s[i],!layer){idxs.push_back(i);}}returnidxs;}IdxgetMul(string_view s){Idx idxs;intlayer0;for(inti0,ns.size();in;i){if(!layeri(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 idxsgetAdd(s);if(idxs.size()){// 最外层是加法运算idxs.push_back(s.size());intlast_idx-1;for(intidx:idxs){resdfs(s.substr(last_idx1,idx-last_idx-1));last_idxidx;}returnres;}// 最外层是乘法运算(或单个字符串)idxsgetMul(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_idx0;res.insert();for(intidx:idxs){resres*dfs(s.substr(last_idx,idx-last_idx));last_idxidx;}returnres;}public:vectorstringbraceExpansionII(string expression){Res resdfs(expression);vectorstringans(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(cins){Solution sol;debug(sol.braceExpansionII(s));}return0;}#endif同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源