NC26 题解 | #括号生成#

题意分析

• 给你一个数字n，需要找到所有的合法的括号序列，括号的个数为n个。

• 前置知识

  • 首先，我们需要知道什么是合法的括号序列？我们知道()这种括号序列是一个合法的序列，)(这种的括号序列不是一个合法的括号序列。那么如果A和B都是合法的括号序列，那么AB也是合法的括号序列，(AB)也是合法的括号序列。
  • 然后，我们需要了解什么是回溯法？回溯法就是在访问某一个子节点的时候，我们将状态改变了，但是为了能够正确地访问另一个子节点，我们需要将状态返回之前访问任何子节点时候的状态。在二叉树上面的体现如下：

+ 最后，我们需要了解一下栈的基本原理和使用。栈是一种先进后出的数据结构。

思路分析

思路一 全排列+栈验证

• 既然，我们这个序列的所有的字符的数量都是固定的，n个左括号和n个右括号，最后的合法的排列一定是这个序列的一种排列的情况。那么我们就可以进行一下处理，我们先将2n个字符构造成一个初始的排列，((((...))))，构造完成之后，我们在利用C++的next_permutation库函数对这个字符串进行全排列，那么怎么验证呢？我们使用栈来模拟一个序列的放入过程。判断这个序列是否合法？

• 代码如下

  • 我们进行了全排列，时间复杂度为n！，然后我们对每个排列进行验证，时间复杂度为n，那么总的时间复杂度为O(n!*n)
  • 每次我们对一个排列进行judge的时候，我们都需要利用一个栈进行处理，空间复杂度为O(n)

    class Solution {
    public:
    /**
    * 
    * @param n int整型 
    * @return string字符串vector
    */
    vector<char> v;
    // 利用栈来验证这个序列是否合法
    bool judge(vector<char> v){
      stack<char> st;
      for(auto x:v){
          // 如果此时栈为空，那么直接push
          if(st.empty()){
              st.push(x);
          }else{
              // 如果可以与栈顶抵消，那么栈顶出栈，否则push
              if(st.top()=='('&&x==')') st.pop();
              else st.push(x);
          }
      }
      return !st.size();
    }
    vector<string> generateParenthesis(int n) {
      // write code here
      // 先构造一个初始的有序的排列
      for(int i=0;i<n;i++){
          v.push_back('(');
      }
      for(int i=0;i<n;i++){
          v.push_back(')');
      }
      vector<string> ans;
      do{
          if(judge(v)){
              string tmp="";
              for(auto x:v){
                  tmp+=x;
              }
              ans.push_back(tmp);
          }
          // 利用permutation函数或得所有的序列组合
      }while(next_permutation(v.begin(),v.end()));
      return ans;
    }
    };

解法二 DFS回溯法

• 回溯法的思想上面进行了介绍，其实这个写法就是上面的一种写法的优化，我们都知道，上面的写法不能再判断此时已知的序列不合法的情况下退出，而是继续进行排列，显然这是浪费时间的。而我们使用DFS回溯法就是在判断这个序列不合法的情况下进行及时退出，避免不必要的遍历。然后因为每个位置可能有两种不同的填法，所以需要进行回溯处理。同时，这里讲一下这个代码里面的sum，因为我们规定的是左括号为1，右括号为-1，那么假如sum<0的时候，此时的左括号一定小于右括号的，这一定是不合法的情况，所以可以直接返回。

• 代码如下

  • 每个位置有两种不同的填法，时间复杂度为O(2^n)
  • 在进行dfs回溯的时候，由于我们的中间数组tmp是全局的，所以这部分空间复杂度为O(n),但是我们发现在每次递归的时候需要使用栈空间，每一层是O(1)，最多n层， 所以是O(n)，最后的空间复杂度为O(n)

    class Solution {
    public:
    /**
    * 
    * @param n int整型 
    * @return string字符串vector
    */
    vector<string> ans;
    vector<char> tmp;
    void dfs(int n,int l,int r,int sum){
      // 如果此时左括号或者右括号都大于n个，或者sum<0，说明此时不合法，直接返回
      if(l>n||r>n||sum<0){
          return;
      }
      // 合法则记录
      if(l==n&&r==n&&sum==0){
          string s;
          for(auto x:tmp){
              s+=x;
          }
          ans.push_back(s);
          return;
      }
      // 先递归将左括号放入的情况
      tmp.push_back('(');
      dfs(n,l+1,r,sum+1);
      // 回溯
      tmp.pop_back();
      // 执行右括号放入的情况
      tmp.push_back(')');
      dfs(n,l,r+1,sum-1);
      // 回溯
      tmp.pop_back();
    }
    vector<string> generateParenthesis(int n) {
      // write code here
      dfs(n,0,0,0);
      return ans;
    }
    };