程序员面试金典——9.6合法序号序列判断

Solution1：我的答案

问题1：判断n对括号序列是否合法。规定合法序列中只包含’(‘和’)‘字符，所以比较容易。’(‘和’)'合法配对即是合法。比较好的方法是基于辅助栈来做。

class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        // write code here
        if(n <= 1)
            return false;
        stack<char> temp;
        temp.push(A[0]);
        for(int i = 1; i < A.size(); i++) {
            if(!temp.empty() && temp.top() == '(' && A[i] == ')')
                temp.pop();
            else 
                temp.push(A[i]);
        }
        if(temp.empty())
            return true;
        else 
            return false;
    }
};

Solution 2:

问题2：
1）n对括号的合法排列个数是多少？
2）打印出n对括号的所有合法排列？
参考网址：https://blog.csdn.net/ffmpeg4976/article/details/42340379?utm_source=blogxgwz0
对于n对括号，合法的排列共有$C(n,2n)-C(n+1,2n)$种.
也就是$\frac{(2n)!}{(n+1)!(n)!}$, 也就是$C(n,2n)/(n+1)$
打印所有排列
解法一：递归。容易理解

#include<iostream>
#include<vector>
#include<string>

using namespace std;

void generate_res(vector<string> &res, string tmp, int left, int right);

int main() {
	int n = 3; //有n对括号
	string tmp = "";
	vector<string> res;
	generate_res(res, tmp, n, n);
	for (auto i : res)
		cout << i << endl;
	return 0;
}

void generate_res(vector<string> &res, string tmp, int left, int right) {
	if (left < 0 || right < left) 
		return;
	if (left == 0 && right == 0) {
		res.push_back(tmp);
		return;
	} else {
		if (left > 0) {
			tmp += '(';
			generate_res(res, tmp, left - 1, right);
			tmp.pop_back();
		}
		if (right > left) {
			tmp += ')';
			generate_res(res, tmp, left, right - 1);
		}
	}
}

解法二：DFS，完全按推导来（不好理解。。）：

vector<string>generate(int n){
    vector<string> result;
    if (n == 0) {
        result.push_back("");
        return result;
    }
    if (n == 1) {
        result.push_back("()");
        return result;
    }
    for (int i = 1; i <= n; i++) {
        vector<string> left = generate(i - 1);
        vector<string> right = generate(n - i);
        for (int j = 0; j < left.size(); j++) {
            for (int k = 0; k < right.size(); k++) {
               result.push_back("("+left[j]+")" + right[k]);
            }
        }
    }
    return result;
}