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;
}
};

NC26 题解 | #括号生成#

题意分析

思路分析

思路一 全排列+栈验证

解法二 DFS回溯法

思路一全排列+栈验证