Keshawn_lu's Blog

Leetcode 32. 最长有效括号

字数统计: 447阅读时长: 2 min
2020/07/04 Share

题目简介:

给定一个只包含 '('')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

1
2
3
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

1
2
3
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

思路:

利用动态规划的思想,dp[i]代表以s[i]为结尾的字符串的有效括号长度。

所以以(为结尾的是不会有有效括号长度的,dp[i] = 0

)为结尾的有两种情况

  1. s[i] = ')' && s[i - 1] = '(',此时dp[i] = dp[i - 2] + 2,即在之前的有效长度上+2。
  2. s[i] = s[i - 1] = ')',此时需要判断s[i - dp[i - 1] - 1]是否等于(
    • dp[i - 1]即前一个字符的有效长度,s[i - dp[i - 1] - 1]即是与s[i]相匹配的括号。
    • 若能匹配上,dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2,即前一个字符的有效长度加上与s[i - dp[i - 1] - 2]字符为结尾的有效长度(之前子串的有效长度)再加上2。

循环时存储长度的最大值,最后返回即可。

tip:

  • 需要注意边界问题,防止数组溢出。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
int longestValidParentheses(string s) {

if(s.empty())
return 0;

vector<int> dp(s.length(), 0);

int max_len = 0;

for(int i = 1; i < s.length(); i++){

if(s[i] == ')' && s[i - 1] == '('){

dp[i] = ((i - 2 >= 0) ? dp[i - 2] : dp[0]) + 2;
}
else if(s[i] == ')' && s[i - 1] == ')'){

if(i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '('){

int pos = (i - dp[i - 1] - 2 >= 0) ? i - dp[i - 1] - 2 : 0;
dp[i] = dp[i - 1] + dp[pos] + 2;
}

}
max_len = max(max_len, dp[i]);
}

return max_len;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: