LeetCode 22 Generate Parentheses

标签: 回溯法 LeetCode 发布于:2022-02-22 17:40:14 编辑于:2022-02-22 18:58:09 浏览量:339

概述

https://leetcode.com/problems/generate-parentheses/

如何保证括号是合法的呢?

回溯法(利用双栈保证合法)

我这里是用两个 stack:

class Solution {
public:
    int n;
    vector<string> ans;
    vector<string> generateParenthesis(int n) {
        this->n = n;
        vector<char> sa;
        vector<char> sb;
        backtrack(sa, sb, 0);
        return ans;
    }
    
    void backtrack(vector<char>& sa, vector<char>& sb, int i) {
        if (i == n && sb.empty()) {
            string t(sa.begin(), sa.end());
            ans.push_back(t);
            return;
        }
        if (!sb.empty()) {
            sb.pop_back();
            sa.push_back(')');
            backtrack(sa, sb, i);
            sa.pop_back();
            sb.push_back(')');
        }
        if (i < n) {
            sa.push_back('(');
            sb.push_back(')');
            backtrack(sa, sb, i + 1);
            sb.pop_back();
            sa.pop_back();
        }
    }
};

由于回溯法的性质(执行完选择后回溯到执行前的状态),后面的那两个 if 的顺序无所谓。

回溯法(依靠剩余的左右括号个数判断是否合法)

如果剩余的右括号个数小于左括号个数,说明不合法。

class Solution {
public:
    vector<string> ans;
    vector<string> generateParenthesis(int n) {
        vector<char> s;
        backtrack(n, n, s);
        return ans;
    }
    
    void backtrack(int l, int r, vector<char>& s) {
        if (l == 0 && r == 0) {
            string t(s.begin(), s.end());
            ans.push_back(t);
            return;
        }
        if (l > r) return;
        if (l > 0) {
            s.push_back('(');
            backtrack(l-1, r, s);
            s.pop_back();
        }
        if (r > 0) {
            s.push_back(')');
            backtrack(l, r-1, s);
            s.pop_back();            
        }
    }
};

关于时间复杂度:

对于 backtrack 函数,状态有三个,分别是 left, right, track,这三个变量的所有组合个数就是 backtrack 函数的状态个数(调用次数)。 left 和 right 的组合好办,他俩取值就是 0~n 嘛,组合起来也就 n^2 种而已;这个 track 的长度虽然取在 0~2n,但对于每一个长度,它还有指数级的括号组合,这个是不好算的。 说了这么多,就是想让大家知道这个算法的复杂度是指数级,而且不好算,这里就不具体展开了,是 4^n / sqrt(n),有兴趣的读者可以搜索一下「卡特兰数」相关的知识了解一下这个复杂度是怎么算的。

https://labuladong.gitee.io/algo/4/29/114/

未经允许,禁止转载,本文源站链接:https://iamazing.cn/