Leetcode 20：有效的括号

题目描述

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

有效字符串需满足：

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

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

代码实现

bool isValid(string s) {
    if (s.empty())
        return true;
    if (s.size() % 2 == 1)
        return false;
    stack<char> tt;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
            tt.push(')');
        else if (s[i] == '[')
            tt.push(']');
        else if (s[i] == '{')
            tt.push('}');
        else if (tt.empty() || tt.top() != s[i])
            return false;
        else
            tt.pop();
    }
    return tt.empty();
}

复杂度

时间复杂度：O(n)，n为字符串长度
空间复杂度：O(n)，n为字符串长度

Leetcode 22：括号生成

题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。例如，给出 n = 3，生成结果为：

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

解题思路

用回溯法可以比较容易的做出来，因为前面回溯法说的比较多了，这里就不再累述。但是有一点注意的是，backtrack()中第三个判断一定要是right<left才可以，而不是right<n，因为right的数量目标是等于left，在已经有了left个左括号的时候，右括号数量right不能超过left。

代码实现

void backtrack(int left,int right, int n, string& s, vector<string>& result)
{
    if (left == n && right == n)
    {
        result.push_back(s);
        return;
    }
    if (left < n) {
        s += "(";
        backtrack(left + 1, right, n, s, result);
        s.pop_back();
    }
    //下面的意思是，右括号不可能多于左括号的数量，当然也不能少于左括号的数量
    if (right < left) {
        s += ")";
        backtrack(left, right + 1, n, s, result);
        s.pop_back();
    }
    
}
vector<string> generateParenthesis(int n) {
    vector<string> res;
    string s;
    backtrack(0, 0, n, s, res);
    return res;
}

复杂度

Leetcode 32：最长有效括号

题目说明

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

解题思路

参考：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/c-liang-ci-bian-li-jie-fa-by-da-li-wang/

代码实现

int longestValidParentheses(string s) {
    int res = 0;
    int left = 0;
    int mark = 0;
    //从左到右
    for (int i = 0; i < s.size(); ++i) {
        int prev_mark = mark;
        mark = max(0, mark + ((s[i] == '(') ? 1 : -1));
        if (mark == 0) {
            if (prev_mark > 0) {
                res = max(i - left + 1, res);
            }
            else {
                left = i + 1;
            }
        }
    }
    mark = 0;
    int right = s.size() - 1;
    //从右到左
    for (int i = s.size() - 1; i >= 0; --i) {
        int prev_mark = mark;
        mark = max(0, mark + ((s[i] == ')') ? 1 : -1));
        if (mark == 0) {
            if (prev_mark > 0) {
                res = max(right - i + 1, res);
            }
            else {
                right = i - 1;
            }
        }
    }
    return res;
}

复杂度

空间复杂度：O(n)【dp数组长度】
时间复杂度：O(n)