典型问题——括号相关的问题¶

以括号为背景的题目在LeetCode出现的频率是很高的，往往只是题目条件做了简单的修改，解题方法会发生很大的变化，涉及的方法从贪心、尺取、递归到动态规划等，所以来做个总结，从中提取最简模型。

括号匹配问题¶

以LeetCode 20 Valid Parentheses为例，这个题目估计是学栈的时候基本都会遇到的问题，所以这类问题也可以认为是**括号有效性类型**的问题。

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

//LeetCode 20 Valid Parentheses
class Solution {
public:
    bool isValid(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        stack<char> store;
        for (auto e : s) {
            switch(e) {
                case '(': case '[': case '{' : 
                    store.push(e); break;
                case ')':
                    if (store.empty() || store.top() != '(') return false;
                    else {store.pop(); break;}
                case ']':
                    if (store.empty() || store.top() != '[') return false;
                    else {store.pop(); break;}
                default:
                    if (store.empty() || store.top() != '{') return false;
                    else store.pop();
            }
        }

        return store.empty();
    }
};

括号生成问题¶

比如LeetCode 22。给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且**有效的**括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

一般这种需要生成所有结果的，常见的思考方向是递归或者深搜。这道题稍加修改就可以伪装成计数问题，比如问给定n，最多可以生成多少组不同的有效的括号，实际上还是生成问题。

//LeetCode 22
class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        solve(0, 0, n, "");
        return res;
    }

    void solve(int left, int right, int n, string tmp)
    {
        if (left == n && right == n) {
            res.push_back(tmp);
            return;
        }

        if (left < n) solve(left + 1, right, n, tmp + "(");
        if (right < left) solve(left, right + 1, n, tmp + ")");
    }
};

括号修改问题¶

**括号修改**问题涉及最多的就是**增加**括号和**删除**括号。比如LeetCode 1249. 移除无效的括号，301. 删除无效的括号，1021. 删除最外层的括号， 921 使括号有效的最少添加（UVA 1626）。

另外还有一种题型，比如给定一串数字和运算符，让添加括号生成不同的结果；或者一个连乘，添加括号让计算次数最小等，虽然是以添加括号为背景，但是很明显，这考察的是区间DP，典型的相似问题就是取石子，所以这种类型的暂时不会归结到这里。

括号计数问题¶

一般这类问题常见的解法就是贪心或动态规划。典型以LeetCode 32最长有效括号为例（扩充形式为洛谷-P1944）。当然贪心也是很好的解法。

//LeetCode  32
class Solution {
public:
    int longestValidParentheses(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = s.size();
        vector<int> d(n + 1, 0);
        int res = 0;
        for (int i = 1; i < n; ++i) {
            if (s[i] == ')' && i > d[i - 1] && s[i - 1 - d[i - 1]] == '(') {
                d[i] = d[i - 1] + 2 + (i - 2 - d[i - 1] >= 0 ? d[i - 2 - d[i - 1]] : 0);
                res = max(res, d[i]);
            }
        }

        return res;
    }
};

括号树¶

典型题目：