Longest Valid Parentheses
Given a string containing just the characters '('
and ')'
, find the length of the longest valid (well-formed) 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.
思路:
首先扫描一遍,mark所有的成对括号。然后数一下最长的记号。
题解:
class Solution { public: int longestValidParentheses(string s) { stack<int> LP; for(int i = 0; i < s.size(); ++i) { char ch = s[i]; if (ch == '(') LP.push(i); else { if (!LP.empty()) { s[LP.top()] = ' '; s[i] = ' '; LP.pop(); } } } int longest = 0; int curr_len = 0; for(auto& ch : s) if (ch == ' ') curr_len++, longest = max(curr_len, longest); else curr_len = 0; return longest; } };