32. 最长有效括号
20200704
难度：困难
题目描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
Solution
栈
class Solution {
public int longestValidParentheses(String s
) {
int ans
= 0;
Stack
<Integer> stack
= new Stack<>();
stack
.push(-1);
for(int i
= 0; i
< s
.length(); i
++){
if(s
.charAt(i
) == '('){
stack
.push(i
);
}else{
stack
.pop();
if(stack
.isEmpty()){
stack
.push(i
);
}else{
ans
= Math
.max(ans
, i
-stack
.peek());
}
}
}
return ans
;
}
}
动态规划
状态：dp[i]代表以下标i字符结尾的最长有效括号的长度状态转移：
若下标i的字符(记为s[i])为(，dp[i] = 0s[i] == ')'
s[i-1] == '('时，dp[i] = dp[i-2] + 2s[i-1] == ')'时,这时要去除中间已经成为有效括号的部分来看，也就是看s[i-dp[i-1]-1]是(还是)
若s[i-dp[i-1]-1] == (，也就是有效括号的长度还会增加，dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2。其中dp[i-1]为中间段，dp[i-dp[i-1]-2] + 2为两边段。
class Solution {
public int longestValidParentheses(String s
) {
int ans
= 0;
int dp
[] = new int[s
.length()];
for(int i
= 1; i
< s
.length(); i
++){
if(s
.charAt(i
) == ')'){
if(s
.charAt(i
-1) == '('){
dp
[i
] = i
>= 2 ? dp
[i
-2] + 2 : 2;
}else if(i
-dp
[i
-1] > 0 && s
.charAt(i
-dp
[i
-1]-1) == '('){
dp
[i
] = dp
[i
-1] + (i
-dp
[i
-1] >= 2 ? dp
[i
-dp
[i
-1]-2] : 0) + 2;
}
ans
= Math
.max(ans
, dp
[i
]);
}
}
return ans
;
}
}
欢迎关注公众号：GitKid，暂时每日分享LeetCode题解，在不断地学习中，公众号内容也在不断充实，欢迎扫码关注
