题目：Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (wellformed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, which has length = 2. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.
以下解法代码的思想及编写参考了网址https://github.com/soulmachine/leetcode#leetcode题解题目
解题代码版本一：
// 使用栈，时间复杂度 O(n)，空间复杂度 O(n)class Solution {public: int longestValidParentheses(string s) { int max_len = 0, last = -1; // the position of the last unmatching ')' stack<int> lefts; // keep track of the positions of non-matching '('s for (int i = 0; i != s.size(); ++i) { if (s[i] == '(') lefts.push(i); else { if (lefts.empty()) // no matching left last = i; else { // find a matching pair lefts.pop(); if (lefts.empty()) max_len = max(max_len, i - last); else max_len = max(max_len, i - lefts.top()); } } } return max_len; }};解题代码版本二：
// 动态规划，时间复杂度 O(n)，空间复杂度 O(n)class Solution {public: int longestValidParentheses(const string& s) { // len 表示从该位置开始的最长有效子字符串长度 vector<int> len(s.size(), 0); int max_len = 0; for (int i = s.size() - 2; i >= 0; --i) { int match = i + len[i + 1] + 1; if (s[i] == '(' && match < s.size() && s[match] == ')') { len[i] = len[i + 1] + 2; if (match + 1 < s.size()) len[i] += len[match + 1]; } max_len = max(max_len, len[i]); } return max_len; }};新闻热点
疑难解答
