题目:https://leetcode-cn.com/problems/longest-valid-parentheses/submissions/
代码:
class Solution {
public int longestValidParentheses(String s) {
if (s==null || s.length()==0){
return 0;
}
int max = 0;
int current = 0;
int sum = 0;
//正向查找
for (int i = 0; i < s.length(); i++) {
sum += s.charAt(i)=='('?1:-1;
current++;
if (sum == 0) {
max = Math.max(max,current);
}else if (sum<0){
current = 0;
sum = 0;
}
}
current = 0;
sum = 0;
//反向查找
for (int i = s.length()-1; i >= 0; i--) {
sum += s.charAt(i)==')'?1:-1;
current++;
if (sum == 0) {
max = Math.max(max,current);
}else if (sum<0){
current = 0;
sum = 0;
}
}
return max;
}
}
思路:因为括号只有()这两种符号,那么暂定(=1,)=-1,那么有效符号字串s转换成数字加减之后。和必定是0。
所以遍历字符串,用current来记录每次遍历字串的长度,在sum=0的时候,认为是一个有效的字串,则将其记录起来(因为只需要最长字串,所以只有当max < current的时候才记录)。在sum < 0的时候,这个时候无论字串后面再来什么符号,这个字串肯定是一个无效的字串,所以我们直接将current和sum清零,并从下一位重新开始寻找新的字串。
以上是正向查找的原因,但是为什么正向查找之后还需要反向查找一次并取两次的最大值呢?目的是解决“(()”这种情况,这种情况下如果正向查找的话因为sum还没有为0过,所以得出结果会为0。因为括号的特殊性,所以将其反向查找一遍。反向查找的时候,则认定)=1,(=-1。其他的类似。具体逻辑见代码。
正向反向分别查找之后,取两者的最大值。则这个最大值就是结果。