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"()()"
class Solution {
public int longestValidParentheses(String s) {
int[] dp = new int[s.length()]; //longest valid parentheses end with current index
Stack<Integer> stack = new Stack<>(); //index of each left parenthese
int ret = 0; for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == '('){
stack.push(i);
}
else if(!stack.empty()){ //')' and have left parenthese in the stack
if(stack.peek() > 0)
dp[i] = dp[stack.peek()-1] + (i-stack.peek()+1);
else //first index
dp[i] = i-stack.peek()+1;
stack.pop();
}
else{ //')' and have no left parenthese in the stack
stack.clear();
}
} for(int i = 0; i < s.length(); i++){
if(dp[i]>ret) ret = dp[i];
}
return ret;
}
}
最长有效括号不仅与当前stack的情况有关,也与有效做括号之前的stack情况有关,所以用动态规划。
使用一维动态规划记录以当前位置结束的最长有效括号。