Halo

A magic place for coding

0%

LeetCode解题报告(335) -- 32. Longest Valid Parentheses

Problem

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1
2
Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

Analysis

  题目给出一个包含左右括号的字符串,要求判断这个字符串中最长的合法的子串长度。因为只有一种括号,所以不需要用栈来判断,用两个值记录左右括号出现的次数就能判断是否匹配上。从左往右遍历,正常来说先是左括号的数量大于右括号的数量,然后当恰好匹配的时候,两者相等,一旦发现右括号的数量较大,则说明已经遍历过的字符串不是有效的。

  按照上面的解法确实可以cover大多数的场景,但是对于题目给出的Example1,好像就不行了。因为左括号的数量是2,右括号的数量是1,两者不相等,所以无法确认合法子串的长度,这种情况我们需要怎么解决呢?

  解决的方法其实非常简单,从右往左再做一遍相同的操作即可。但是判断的条件关系恰好相反,先是右括号的数量大于左括号的数量,然后当两者数量相等时,说明恰好匹配,一旦发现左括号的数量较大,则重置。


Solution

  无


Code

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
class Solution {
public:
int longestValidParentheses(string s) {
int left = 0, right = 0;
int size = s.size(), result = 0;
for (int i = 0; i < size; i++) {
s[i] == '(' ? left++: right++;
if (left == right) {
result = max(result, left * 2);
} else if (right > left) {
left = right = 0;
}
}

left = right = 0;
for (int i = size - 1; i >=0; i--) {
s[i] == '(' ? left++: right++;
if (left == right) {
result = max(result, left * 2);
} else if (left > right) {
left = right = 0;
}
}
return result;
}
};

Summary

  这是一道比较简单的括号匹配题目,这里主要利用了两遍遍历来解决。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels