tag:
- Hard;
- Dynamic Programming;
question:
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 "()()"
思路：
1. 栈解法：
需要利用一个变量start来记录有效子串的起始下标，res表示答案。
遍历所有字符
- 如果当前字符s[index]为'('，将index入栈
- 否则判断栈是否为空：
- 如果为空，则说明这个右括号无效，不影响结果，start = index + 1
- 如果不为空，则出栈，即找到一个左括号和它匹配
- 如果栈空，则说明从start到index的匹配完了，res = max(res, index - start + 1)
- 如果栈不为空，则res = max(res, index - s[栈顶])，即栈顶+ 1 ~~ index都匹配了
class Solution {
public:
int longestValidParentheses(string s) {
int res=0, start=0;
stack<int> m;
for(int i=0; i<s.size(); ++i) {
if(s[i] == '(')
m.push(i);
else {
if(m.empty())
start = i+1;
else {
m.pop();
res = m.empty() ? max(res, i-start+1) : max(res, i-m.top());
}
}
}
return res;
}
};
2. DP解法：
一般对于最长XX问题容易想到利用DP求解，在这题中利用逆向DP，设状态dp[i]为从i到len - 1中，以i开头的最长合法子串长度：
- 初始化：dp[len - 1] = 0
- 如果s[i] = ')'，则跳过，因为不可能有由'('开头的串
- 如果s[i] = '('，则需要找到右括号和它匹配，可以跳过以i + 1开头的合法子串，则需要看j = i + dp[i + 1] + 1是否为右括号。如果没越界且为右括号，那么有dp[i] = dp[i + 1] + 2，此外在这个基础上还要将j + 1开头的子串加进来（只要不越界）
class Solution {
public:
int longestValidParentheses(string s) {
if (s.empty()) return 0;
vector<int> dp(s.size(), 0);
int res = 0;
for (int i=s.size()-2; i>=0; --i) {
if (s[i] == '(') {
int j = i + dp[i+1] + 1;
if (s[j] == ')' && j < s.size()) {
dp[i] = dp[i+1] + 2;
if (j+1 < s.size())
dp[i] += dp[j+1];
}
res = max(res, dp[i]);
}
}
return res;
}
};
