作者:黄石幽兰it | 来源:互联网 | 2023-09-11 10:50
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.
思路:DP。
dp[i]记录最后一位是s[i]的最长合法串的长度。
很明显,当s[i] = ‘(‘时dp[i] = 0。
当s[i] = ‘)‘ 时,如果i不为0的话(为0肯定dp[i] = 0),则看一下dp[i - 1]记录的最长串的值。
而i - 1 - dp[i - 1]就是最后一位是s[i - 1]的最长合法串的前面一个字符的位置。
当dp[i - 1]等于0时,即没有合法串,该值正好是i - 1本身,而大于0时,则正好是合法串前面一位的下标。
如果s[i - 1 - dp[i - 1]]是‘(‘的话,就正好能和当前i位置的‘)‘匹配,从而合法串长度等于dp[i - 1] + 2。
但要注意一下,加入有如下情况,"()(())",当我们到了最后一位时,按照这个方法计算出的dp[i]=4,实际上应该为6,因为这样做忽略了前面还可能有能连起来的合法串。因此这里我们还要判断下i - 2 - dp[i - 1]是否大于等于0,如果是的话,则dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]。
1 class Solution {
2 public:
3 int longestValidParentheses(string s) {
4 int n = s.size(), res = 0;
5 vector<int> dp(n, 0);
6 for (int i = 1; i )
7 {
8 if (s[i] == ‘(‘)
9 dp[i] = 0;
10 else if (i - dp[i - 1] - 1 >= 0
11 && s[i - dp[i - 1] - 1] == ‘(‘)
12 dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ?
13 dp[i - dp[i - 1] - 2] : 0);
14 res = max(res, dp[i]);
15 }
16 return res;
17 }
18 };