0%

leetcode 32 Longest Valid Parentheses

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 "()()" 题目地址:leetcode Longest Valid Parentheses

题目大意:给你一个括号组成的字符串,要求求出最长的合法括号长度

一开始想,每次计算的时候用当前右括号,合法长度的开头,但是有

)(((((()())()()))()(()))( 应该为22. 而我合法长度的开头从1开始,因为后面没有匹配第一个和第二个左括号的,所以wa了。

后来开了个数组Match,用来标记当前左括号和哪个右括号匹配。

之后进行一次扫描,过程主要如下:

  • 用temp标记合法连续的上一块总长度
  • 若match[i]!=0, 每次i移动的位置直接移动到右括号的位置(即match[i]),因为这一段必定是合法的。
  • 更新ans

 

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
27
28
29
30
31
32
33
34
35
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> q;
int len = s.length();
int *match = new int[len];

for (int i = 0; i < len; i++){
match[i] = 0;
if (s[i] == ')' && !q.empty()){
match[q.top()] = i;
q.pop();
}
else if (s[i] == '(')
q.push(i);
}

int temp = 0, ans = 0;
for (int i = 0; i < len; i++){
if (!match[i]) continue;

if (temp + match[i] - i + 1> ans)
ans = temp + match[i] - i + 1;

if ( match[i] + 1 < len && match[ match[i] + 1] == 0)
temp = 0;
else
temp = temp + match[i] - i + 1;
i = match[i];
}

delete[] match;
return ans;
}
};

 

之后搜了别人怎么做的。

有的直接用个bool数组标记括号是否匹配,如果匹配为1,之后进行统计即可。 更简单一些。

参考代码如下:

c++:

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
27
28
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> q;
int len = s.length();
bool *match = new bool[len];

for (int i = 0; i < len; i++){
match[i] = 0;
if (s[i] == ')' && !q.empty()){
match[q.top()] = match[i]=true;
q.pop();
}
else if (s[i] == '(')
q.push(i);
}

int temp = 0, ans = 0;
for (int i = 0; i < len; i++){
if (!match[i]) { temp = 0; continue; }
temp++;
ans = ans < temp ? temp : ans;
}

delete[] match;
return ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
# @param s, a string
# @return an integer
def longestValidParentheses(self, s):
stack=[]
match=[0 for i in range(0,len(s))]
for i,c in enumerate(s):
if c == '(':
stack.append(i)
elif c==')' and len(stack)!=0:
match[i]=match[stack[-1]]=1
stack.pop()

ans ,temp=0,0
for i,c in enumerate(match):
if match[i]:
temp=temp+1
ans= max(ans,temp)
else:
temp=0
return ans

 

还可以用栈记录上一个括号的位置和之前连续的长度。

若能和上一段拼接起来,就合并。合并比(())()这种情况,最后一个)的时候,发现可以和之前的合并。

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
27
28
class Solution {
public:
int longestValidParentheses(string s) {
int ans = 0, cur = 0;
stack<pair<int, int>> q;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == ')') {
if (q.empty())
cur = 0;
else {
pair<int, int> t = q.top();
cur += t.second + 2;
q.pop();
if (!q.empty() && q.top().first == i - cur + 1) {
cur += q.top().second;
q.pop();
}
ans = max(ans, cur);
}
}
else {
q.push(make_pair(i,cur));
cur = 0;
}
}
return ans;
}
};

 

下面是最简洁的写法了,

  • 遇到(就把下标放入,
  • 遇到)就先pop一个,

    • 如果栈为空,说明没匹配,把当前下标push进去,作为新的一段的开始
    • 栈不为空,说明合法,长度为i - 栈顶的下标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int longestValidParentheses(string s) {
int ans = 0, cur = 0;
stack<int> q;
q.push(-1);
for (int i = 0; i < s.size(); ++i) {
if (s[i] == ')') {
q.pop();
if (q.empty())
q.push(i);
else
ans = max(ans, i - q.top());
}
else {
q.push(i);
}
}
return ans;
}
};
请我喝杯咖啡吧~