LeetCode #22 括号生成

class Solution {
public:
    map<string,int> hash={{"(",1},{")",-1}};
    bool canaddRight(string str){
        int i=0;
        string s;
        int j;
        for(j=0;j<str.size();j++){
            s=str.substr(j,1);
            i+=hash[s];
        }
        return i;
    }
    int count(string str){
        int i=0;
        string s;
        int j;
        for(j=0;j<str.size();j++){
            s=str.substr(j,1);
            i+=hash[s]==1?1:0;
        }
        return i;
    }
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        queue<string> p;
        if(n==0){
            return ans;
        }
        p.push("(");
        string s,s_;
        while(!p.empty()){
            s=p.front();
            if(s.size()==2*n-1){
                ans.push_back(s+")");
            }
            else{
                if(canaddRight(s)){
                    p.push(s+")");
                }
                if(count(s)<n){
                    p.push(s+"(");
                }
            }
            p.pop();
        }
        return ans;
    }
};

这道题基本上就是两种思路，遍历或者动态规划（状态转移），遍历是用时间换空间，遍历是用空间换时间（存储所有n小的状态来减少遍历）。