C++ AC non-recursion solution with a queue


  • 0
    H
    class Solution {
    public:
    	vector<string> generateParenthesis(int n) {
    		vector<string> result;
    		if (n == 0) return result;
    		queue<string> strQueue;
    		queue<pair<int, int>> resQueue;
    		strQueue.push("(");
    		resQueue.push(make_pair(n - 1, n));
    		while (!strQueue.empty()){
    			string curStr = strQueue.front();
    			if (curStr.size() == 2 * n)
    				break;
    			strQueue.pop();
    			pair<int, int> curNum = resQueue.front();
    			resQueue.pop();
    			if (curNum.first != 0){
    				strQueue.push(curStr + "(");
    				resQueue.push(make_pair(curNum.first - 1, curNum.second));
    			}
    			if (curNum.first < curNum.second){
    				if (curNum.second == 1)
    					result.push_back(curStr + ")");
    				else {
    					strQueue.push(curStr + ")");
    					resQueue.push(make_pair(curNum.first, curNum.second - 1));
    				}
    			}
    		}
    		return result;
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.