LeetCode

LeetCode-22 括号生成

nkul · 9月30日 · 2020年 · 25次已读

本题是个比较典型的dfs,类似上题,有效的括号对,需要每个右括号进行匹配。即栈中左一定大于右,才是合法的。

1、对于一个括号,如果左还剩就可以放左

2、只要右还剩,且栈中左大于右,就可以放

3、时间复杂度就是合法括号数,是个常数为卡特兰数

class Solution {
public:
    vector res;
    vector generateParenthesis(int n) {
        dfs(n,0,0,"");
        //res.size() ==卡特兰数 
        return res;
    }

    void dfs(int n,int lc , int rc,string path){
        if(lc == n && rc == n) res.push_back(path);
        else{
            //有左括号都可以放
            if(lc < n) dfs(n,lc + 1, rc, path+'(');
            //放右括号的前提是,path中左括号数量大于右括号
            if(rc < n && lc > rc) dfs(n,lc, rc + 1, path+')');
        } 
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!