Leetcode22. 括号生成

2021年8月9日 690点热度 1人点赞 0条评论

题目描述

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8

解题思路

算法描述

这道题考虑用暴力的方法,那么就是考虑DFS或者BFS两种方式。一般由于DFS的编码比较简单而选择DFS的方法。同时,在暴力的同时尽可能考虑剪枝。

首先一种最简单的暴力的方法就是将所有可能的括号序列列出来,然后写一个函数去判断这个序列是不是合理的。这种方法思路很简单,但是递归的时候有很多无用的路径,所以可以通过剪枝的方法优化一下,保证在加入(或者)后序列仍然有效的条件下才进行递归。

那么关键就在于如何保证加入括号后序列仍然保持有效。通过观察归纳,我们可以得出以下两个加入括号的条件:

  • 左括号:在左括号的数量left小于给定的对数n的时候都可以加入左括号;
  • 右括号:只有在右括号的数量right小于左括号数量left的时候才能加入右括号;

这样就可以写出DFS的代码。

参考代码

void DFS(vector<string>& ans, string& cur, int left, int right, int n){
    if(cur.size() == n * 2){
        ans.push_back(cur);
        return;
    }

    if(left < n){
        cur.push_back('(');
        DFS(ans,cur,left+1,right,n);
        cur.pop_back();
    }

    if(right < left){
        cur.push_back(')');
        DFS(ans,cur,left,right+1,n);
        cur.pop_back();
    }
}

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

复杂度分析

这个的复杂度分析比较复杂,不要求掌握。

时间复杂度:$O(\frac{4^n}{\sqrt{n}})$​

空间复杂度:$O(n)$

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

您需要 登录 之后才可以评论