Leetcode每日一题 —— 1096. 花括号展开 II

佬友中秋节快乐啊！中秋节竟然上强度了…这题算是学到了神奇的 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;

    }

};