LeetCode Hot100 DFS经典题型：括号生成

前言

最近再刷LeetCode的时候，写了一道DFS题型，自己一开始没想到好的办法，后来经过一步步优化超过C++提交的100%。由此记录。
先上题目：

思路

一看到这种题型和数据范围，直接想到DFS暴搜一次就可以了。
对于最终字符串，我们可以一步一步加括号，然后括号用完了就判断是否符合题目意思，如果符合，那么就把这个字符串加入到最终结果；否则就return。

代码实现

class Solution {
public:

    vector<string> ans;

    vector<string> generateParenthesis(int n) {
        dfs(n * 2, "", n);
        return ans;
    }

    void dfs(int u, string s, int n){
        if(u < 0) return;
        if(u == 0){
            if(judge(s)){
                ans.push_back(s);
            }
            return;
        }
        dfs(u - 1, s + "(", n);
        
        dfs(u - 1, s + ")", n);
    }

    bool judge(string s){
        stack<int> st;
        for(int i = 0; i < s.size(); i++){
            if(st.size() == 0) {
                if(s[i] == '(') st.push(s[i]);
                else return false;
            }
            else{
                if(s[i] == '(') st.push(s[i]);
                else {
                    if(st.top() == '('){
                        st.pop();
                    }
                }
            }
        }
        return st.size() == 0;
    }
};

优化一

假设当前字符串为s，假设剩余的左括号有l个，剩余的右括号有r个。假如现在左括号剩余数目大于右括号剩余数目，意思就是说当前字符串s的右括号数目是大于左括号数目，比如n = 3的时候，当前字符串s = ())，那么即使一直递归下去，当前字符串s已经不满足条件了，那么之后就更加不满足了，所以当左括号剩余数目大于右括号剩余数目的时候，此时可以剪枝。我们直接return就可以了。

class Solution {
public:

    vector<string> ans;

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

    void dfs(int l, int r, string s, int n){
        if(l < 0 || r < 0 || l > r) return;
        if(l + r == 0){
            if(judge(s)){
                ans.push_back(s);
            }
            return;
        }
        dfs(l - 1, r, s + "(", n);
        
        dfs(l, r - 1, s + ")", n);
    }

    bool judge(string s){
        stack<int> st;
        for(int i = 0; i < s.size(); i++){
            if(st.size() == 0) {
                if(s[i] == '(') st.push(s[i]);
                else return false;
            }
            else{
                if(s[i] == '(') st.push(s[i]);
                else {
                    if(st.top() == '('){
                        st.pop();
                    }
                }
            }
        }
        return st.size() == 0;
    }
};

优化二

由于优化一，我们现在发现不需要judge方法去判断当前字符串是否合法。因为优化一的方法是不允许出现右括号数目大于左括号数目的，（因为当右括号数目大于左括号数目的时候我们return了）。所以当遍历到最后的时候，该字符串一定是合法的，所以我们直接插入到答案里面就可以了。

class Solution {
public:

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

    void dfs(int l, int r, string s, int n){
        if(l < 0 || r < 0 || l > r) return;
        if(l + r == 0){
             ans.push_back(s);
            return;
        }
        dfs(l - 1, r, s + "(", n);
        
        dfs(l, r - 1, s + ")", n);
    }
};