1087. Brace Expansion ----M

 A string S represents a list of words.

Each letter in the word has 1 or more options.  If there is one option, the letter is represented as is.  If there is more than one option, then curly braces delimit the options.  For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].

Return all words that can be formed in this manner, in lexicographical order.

 

Example 1:

Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: "abcd"
Output: ["abcd"]

 

Note:

1. 1 <= S.length <= 50
2. There are no nested curly brackets.
3. All characters inside a pair of consecutive opening and ending curly brackets are different.

A:

就是个Permuation 的问题

一层层加上去就是了

class Solution {
public:
    vector<string> expand(string S) {
        vector<vector<char>> V;
        int start = 0;
        int n = S.length();
        while(start<n){
            int end = start;
            if(S[end]!= '{'){
                V.push_back(vector<char>{S[end]});
                start++;
            }else{
                while(end<n && S[end]!='}'){
                    end++;
                }
                V.push_back(vector<char>());
                for(int i =start+1;i<end;i+=2){
                    V.back().push_back(S[i]);
                }
                start = end+1;
            }
        }
        //
        vector<string> res;
        if(V.size()==0)
            return res;
        res.push_back("");
        for(auto line : V){
            vector<string> newRes;
            for(auto ch : line){
                for(auto& t : res){
                    newRes.push_back( t+ string(1,ch) );
                }
            }
            res = newRes;
        }
        sort(res.begin(), res.end()); // sort in Lexicographical order
        return res;
    }
};