0 ms High performance C++ iterative solution


  • 0
    W
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        if (!n) return result;
        
        string s(n, '(');
        s.append(n, ')');
    
        // record the back of str to avoid memory allocation for better performance
        int back = s.size() - 1;  
        for (;;) {
            auto l = n, r = n;
            result.push_back(s);
            for (;;) {
                if (s[back] == ')') --r;
                else if (l < r + 2) --l;
                else break;
                if (--back < 0) return result;
            }
            
            s[back] = ')';
            for (auto dest = back + n - l + 1; back != dest; s[++back] = '(');
            for (auto dest = s.size() - 1; back != dest; s[++back] = ')');
        };
    }

Log in to reply
 

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