LeetCode 1087. 字母切换（回溯）

示例 1：
输入："{a,b}c{d,e}f"
输出：["acdf","acef","bcdf","bcef"]

示例 2：
输入："abcd"
输出：["abcd"]
 
提示：
1 <= S.length <= 50
你可以假设题目中不存在嵌套的花括号
在一对连续的花括号（开花括号与闭花括号）之间的所有字母都不会相同

class Solution {
	vector<string> ans;
public:
    vector<string> expand(string S) {
    	vector<vector<char>> str;
    	vector<char> t;
        int count = 0;
    	for(int i = 0; i < S.size(); ++i)
    	{
    		if(isalpha(S[i]))
    			t.push_back(S[i]);
    		else if(S[i] == '}' || (S[i] == '{' && !t.empty()))
    		{
                if(S[i] == '}') count++;
    			sort(t.begin(), t.end());
    			str.push_back(t);
    			t.clear();
    		}
    	}
        if(!t.empty())
        {
            sort(t.begin(), t.end());
    		str.push_back(t);
        }
        if(count == 0) return {S};//没有花括号，直接返回
    	dfs(str, "", 0);
    	return ans;
    }

    void dfs(vector<vector<char>>& str, string s, int i)
    {
    	if(i == str.size())
    	{
    		ans.push_back(s);
    		return;
    	}
    	for(int j = 0; j < str[i].size(); ++j)
    		dfs(str, s+str[i][j], i+1);
    }
};