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)