0032. Longest Valid Parentheses - kumaeki/LeetCode GitHub Wiki
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Example 3:
Input: s = ""
Output: 0
Constraints:
- 0 <= s.length <= 3 * 104
- s[i] is '(', or ')'.
Dynamic Programming
最后的结果一定是偶数 或者 0
定义数组DP , DP[ i ]表示一定包含 s[i] 字符的连续有效的字符串总长度
如果当前字符为 ( 那么一定为0
如果当前字符为 ) 那么根据之前的计算结果得到当前值
public class Solution {
public int longestValidParentheses(String s) {
int len = s.length(), res = 0;
int[] dp = new int[len];
for (int i = 1; i < len; i++) {
if (s.charAt(i) == ')') {
int pre = s.charAt(i - 1);
if (pre == '(')
dp[i] = (i > 1 ? dp[i - 2] : 0) + 2;
else if (i - 1 - dp[i - 1] >= 0 && s.charAt(i - 1 - dp[i - 1]) == '(')
dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0);
res = Math.max(res, dp[i]);
}
}
return res;
}
}Stack
用stack来保存当前字符的位置i
如果s[ i ] = '(', 把 i存入stack
否则, 弹出stack的顶点, stack为空, 将当前i存入stack, 否则 计算当前位置和顶点的距离.(这个距离的最大值就是答案)
public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
int res = 0;
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
res = Math.max(res, i - stack.peek());
}
}
return res;
}
}双向计数
从左往右, 每遇到一个 "(" 则+1, 如果遇到 ")" 则 - 1. 那么为0的时候 就是正好表达式有效, 求得长度就可以了. 如果计数小于0 , ")"多了一个, 无论后面的字符是什么, 都不能使表达式有效, 那么重新开始计数.
我们从倒序(右往左)再算一次,然后取两次的最大值就好了.
注意计数规则要和顺序(从左往右)反过来, 遇到"(" 则-1, 遇到 ")" 则 + 1
public class Solution {
public int longestValidParentheses(String s) {
return Math.max(helper1(s), helper2(s));
}
private int helper1(String s) {
int balance = 0, max = 0, count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(')
balance++;
else
balance--;
if (balance >= 0) {
count++;
if (balance == 0)
max = Math.max(max, count);
} else {
count = 0;
balance = 0;
}
}
return max;
}
private int helper2(String s) {
int balance = 0, max = 0, count = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == ')')
balance++;
else
balance--;
if (balance >= 0) {
count++;
if (balance == 0)
max = Math.max(max, count);
} else {
count = 0;
balance = 0;
}
}
return max;
}