leetcode:22. bracket-generating

22. Bracket generation

source ： Power button （LeetCode）

link : https://leetcode.cn/problems/generate-parentheses/

Numbers n Represents the logarithm of the generated bracket , Please design a function , Used to be able to generate all possible and Effective Bracket combination .

Example 1：

 Input ：n = 3
 Output ：["((()))","(()())","(())()","()(())","()()()"]

Example 2：

 Input ：n = 1
 Output ：["()"]

Tips ：

• 1 <= n <= 8

solution

• Judge whether it is legal after all combinations are generated ： First use recursion to generate all possible extension combinations , Then we can judge whether each bracket combination is legal ;
• Based on the relationship between brackets , We can know whether it is a legal combination while generating parentheses ： The number of bracket pairs is n, Then the number of left parentheses is also n individual , The left parenthesis can be put in at any time , As long as the number of left parentheses does not exceed n individual , For the right parenthesis, consider the number of left parentheses , When the number of right parentheses is less than the number of left parentheses , It can be put in , in addition , The right parenthesis cannot exceed n individual . But since the left bracket is not greater than n Of , So when the number of right parentheses is less than or equal to the number of left parentheses This limit has been met .
• Use parentheses and n-1 The results of any combination ： among n Recursion to 1; And then ’()' Put it in n-1 Any position in the result is sufficient , String splicing ;

Code implementation

Generate all combinations recursively first , Then judge the legitimacy

python Realization

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []

        #  All possible combinations of Mister , And judge whether each combination meets the standard 
        def helper(ss=[]):
            if len(ss) == 2*n:
                if self.valid(''.join(ss)):
                    ans.append(''.join(ss))
            else:
                ss.append('(')
                helper(ss)
                ss.pop()
                ss.append(')')
                helper(ss)
                ss.pop()
        
        helper()
        return ans
    
    def valid(self, s):
        counts = 0
        for char in s:
            if char == '(':
                counts += 1
            else:
                counts -= 1

            if counts < 0:
                return False
        return counts == 0 

c++ Realization

class Solution {
    
private:
    vector<string> ans;

public:
    bool valid(string s) {
    
        int counts = 0;
        for(char ch: s) {
    
            if (ch == '(')
                counts++;
            else
                counts--;
            if (counts < 0)
                return false;
        }
        return counts == 0;
    }

    string convert(vector<char> cs, int size) {
    
        string s;
        for(int i=0; i<size; i++)
            s += cs[i];
        return s;
    }

    void _generateParenthesis(vector<char> cs, int n) {
    
        if (cs.size() == 2 * n) {
    
            string s = convert(cs, 2*n);
            if (valid(s))
                ans.push_back(s);
        }
        else {
    
            cs.push_back('(');
            _generateParenthesis(cs, n);
            cs.pop_back();
            cs.push_back(')');
            _generateParenthesis(cs, n);
            cs.pop_back();
        }
    }

    vector<string> generateParenthesis(int n) {
    
        _generateParenthesis({
    }, n);
        return ans;
    }
};

Complexity analysis

• Time complexity ： $O(2^{2n}\ast n)$
• Spatial complexity ： $O(n)$

Recursively generated and combined deletion based on the number of left and right parentheses

python Realization

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []

        def helper(l, r, s):
            #  Recursion end condition 
            if len(s) == 2*n:
                ans.append(s)
            
            if len(s) > 2 * n:
                return
            
            #  Start to deal with 
            if l < n:
                helper(l+1, r, s+'(')
            if r < l and r < n:
                helper(l, r+1, s+')')
        
        helper(0, 0, '')
        return ans

c++ Realization

class Solution {
    
private:
    vector<string> ans;

public:
    int _generateParenthesis(int left, int right, int n, string s) {
    
        if (s.size() == 2 * n)
            ans.push_back(s);
        
        if (s.size() > 2*n)
            return -1;

        if (left < n)
            _generateParenthesis(left+1, right, n, s+'(');
        if (right < left)
            _generateParenthesis(left, right+1, n, s+')');
        return 0;
    }

    vector<string> generateParenthesis(int n) {
    
        _generateParenthesis(0, 0, n, "");
        return ans;
    }
};

Complexity analysis

"()" And n-1 Any string concatenation of the result

python Realization

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 1:
            return ['()']
        
        res = set()
        
        for i in self.generateParenthesis(n-1):
            for j in range(len(i)+2):
                res.add(i[0:j] + '()' + i[j:])
        return list(res)

c++ Realization

class Solution {
    
public:
    vector<string> generateParenthesis(int n) {
    
        if (n==1)
            return {
    "()"};
        
        unordered_map<string, int> mp;
        vector<string> res;

        string tmp;
        for (auto& s: generateParenthesis(n-1)) {
    
            for (int i=0; i < 2*(n-1); i++) {
    
                tmp = s.substr(0, i) + "()" + s.substr(i, 2*(n-1));
                if (mp[tmp] == 0) {
    
                    ++mp[tmp];
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
};

Complexity analysis