Leetcode 32. Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”
Example 2:
Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”
解析：
最大括号匹配问题。是对问题Valid Parentheses问题的升级。
解法1:栈
这里要求匹配最长的括号，需要记录最长的开始位置，采用栈来存储括号开始位置的下标，定义遍历start用来记录括号的开始位置。如果当前字符是(，则将当前下标入栈；如果是)，但是此时栈为空，则把当前下标付给start，如果栈非空，则出栈，此时需要判断栈是否为空，如果为空，则res为max(res, i-start)，如果栈不为空，则res=max(res,i-st.top())。另外需要注意，初始start初始化为-1，是为了处理第一个位置就匹配的情况，如”(())”,最后时i=3,start=-1,最大长度为i-start=4.
代码如下：
[cc lang=”C++”]
class Solution {
public:
int longestValidParentheses(string s) {
stack
int res = 0;
int start = -1;
for(int i=0; i < s.size(); i++)
{
if(s[i] == '(')
st.push(i);
else
{
if(st.empty())
start = i;
else
{
st.pop();
if(st.empty())
res = max(res, i -start);
else
res = max(res, i - st.top());
}
}
}
return res;
}
};
[/cc]
运行结果：
解法2:动态规划
假设dp[i]表示以字符s[i-1]结尾的合法括号子串的最大长度。递推公式的推导直接拿别人的分析过程吧。
代码如下：
[cc lang=”C++”]
class Solution {
public:
int longestValidParentheses(string s) {
int max_len = 0;
vector
for (int i = 1; i <= s.length(); ++i) {
int j = i - 2 - dp[i - 1];
if ('(' == s[i - 1] || j < 0 || ')' == s[j]) {
dp[i] = 0;
} else {
dp[i] = dp[i - 1] + 2 + dp[j];
max_len = max(max_len, dp[i]);
}
}
return max_len;
}
};
[/cc]
参考：
https://leetcode.com/problems/longest-valid-parentheses/discuss/14167/Simple-JAVA-solution-O(n)-time-one-stack
https://www.youtube.com/watch?v=AqnGU4RjrxY
http://zhuixin8.com/2016/10/02/leetcode-32/
About Author
