题目
给定一个字符串s，由 '(' 和 ')' 组成，求最长合法括号(valid parentheses)长度
例
"((()())("，合法段为"(()())"，长度为6
解法
这种求最长xxx的题目很容易想到动态规划，使用一个数组vector<int> dp记录 由s[i]作为最后一个字符的字符串的substring的长度
例
"((()())(": [0, 0, 0, 2, 0, 4, 6, 0]
每个字符s[i]的情况如下
- '(':
dp[i] = 0 // '(' 不可能是任意一个合法括号的结尾
不需要操作，因为初始为0 - ')':
最长长度增加2，因为增加了一组括号"()"，但在哪个substring的基础上增加2需要继续讨论- s[i - 1] == '(': 直接在dp[i - 1]的基础上增加2
- s[i - 1] == ')': 这个情况比较复杂，s[i - 1]可能是一个合法括号组合的结尾，我们需要找出以s[i - 1]为结尾的substring之前的那个元素，
- s[i - 1] == '(': 该 '(' 与s[i] 包括这两个元素之间的元素组成了一个更长的valid parentheses(下面写如何找出这个元素)。如果在这个新的substring之前也是valid parentheses，那么新的长度也需要加上这个前面的substring长度(dp[i - 1 - dp[i - 1]])
')': 不是valid parentheses，不用理他
如何找出这个元素
dp[i - 1] 记录了 s[i]之前的substring的长度，用i - 1减去长度就得到了我们要找的那个元素
s: "( ( ) ( ) )"
dp: [0, 0, 2, 0, 2, 0]
i = 5: s[i] == ')', s[i - 1] = ')' 我们要找找出以s[i - 1]结尾的substring之前的那个元素也就是s[0], 也就是s[i - 1 - dp[i - 1]];
// 不要忘记检查位序是否合法
代码
class Solution {
public:
int longestValidParentheses(string s) {
if (s.size() < 2) return 0;
vector<int> dp(s.size(), 0);
int max_len = 0;
for (int i = 1; i < s.size(); i++) {
if (s[i] == ')') {
if (s[i - 1] == '(') {
dp[i] = ((i >= 2) ? dp[i - 2] : 0) + 2;
max_len = max(max_len, dp[i]);
} else {
// dp[i - 1] == ')'
if ((i - 1 - dp[i - 1]) >= 0 and s[i - 1 - dp[i - 1]] == '(') {
dp[i] = dp[i - 1] + 2 + ((i - 1 - dp[i - 1] >= 2) ? dp[i - 2 - dp[i - 1]] : 0);
max_len = max(max_len, dp[i]);
}
}
}
}
return max_len;
}
};
