[LeetCode] 32. Longest Valid Parentheses

题目

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

标签

String, Dynamic Programming, Stack

分析

TBD

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class Solution {
public:
/*
* two traverse
*/
int longestValidParentheses(string s) {
int left, right, stack, len;
left = len = 0;
// traverse from left to right
while (left < (int)s.length()) {
while (left < (int)s.length() && s[left] == ')') left++;
right = left;
stack = 0;
while (right < (int)s.length()) {
// stack = Nums(left parentheses) - Nums(right parentheses)
if (s[right] == '(') stack++;
else if (s[right] == ')') {
stack--;
if (stack == 0) len = max(len, right - left - stack + 1);
else if (stack < 0) break;
}
right++;
}
left = right;
}

right = (int)s.length() - 1;
// traverse from right to left
while (right >= 0) {
while (right >= 0 && s[right] == '(') right--;
left = right;
stack = 0;
while (left >= 0) {
// stack = Nums(right parenth) - Nums(left parenth)
if (s[left] == ')') stack++;
else if (s[left] == '(') {
stack--;
if (stack == 0) len = max(len, right - left - stack + 1);
else if (stack < 0) break;
}
left--;
}
right = left;
}
return len;
}

/*
* using stack
*/
int longestValidParentheses_stack(string s) {
stack<int> st;
int len = 0;
// always store the start index in the bottom of stack.
// -1 at start, index of last unmatched right parenthesis when traversing.
st.push(-1);
for (int i = 0; i < (int)s.length(); i++) {
if (s[i] == '(') st.push(i);
else {
st.pop();
// empty means all left parentheses were run out
if (st.empty()) st.push(i);
else len = max(len, i - st.top());
}
}
return len;
}


/*
* using dynamic programming
*/
int longestValidParentheses_dp(string s) {
if (s.length() <= 1) return 0;
int dpArray[s.length() + 1];
dpArray[0] = dpArray[1] = 0;
dpArray[2] = (s[0] == '(' && s[1] == ')')? 2 : 0;
int len = dpArray[2];
for (int i = 2; i < (int)s.length(); i++) {
int ii = i + 1;
if (s[i] == '(') dpArray[ii] = 0;
else {
if (s[i-1] == '(') dpArray[ii] = dpArray[ii-2] + 2;
else {
if (i > dpArray[ii-1] && s[i - dpArray[ii-1] - 1] == '(')
dpArray[ii] = dpArray[ii-1] + 2 + dpArray[i-dpArray[ii-1]-1];
else dpArray[ii] = 0;
}
}
len = max(len, dpArray[ii]);
}
return len;
}
};k