#Problem

#⭐️⭐️⭐️⭐️⭐️

Longest Valid Parentheses substring

#Solution

#Solution #1 - Brute Force

两层for loop穷举所有的substring, 每次再利用一个for loop和stack判断substring是否是valid.

Time: O(N^3 )

#Solution #2 - Dynamic Programming

dp[i] represents longest valid parentheses that ends with i-th character.

dp[i] = dp[i - 2] + 2, if chs[i - 1] == ‘(‘ && chs[i] == ‘)’
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2, if chs[i - 1] == ‘)’ && chs[i] == ‘)’ && chs[i - dp[i - 1] - 1] == ‘(‘

#Solution #3 - Stack
  • 碰到开括号’(‘, 入栈
  • 碰到闭括号’)’:
    • 如果当前栈为空, 比如”)()”这种第一个就是闭括号的. 那么 start = i; (这一步是关键)
    • 如果当前栈不为空, 出栈.
      • 如果此时栈为空, len = i - start;
      • 如果此时栈不为空, len = i - stk.peek();
    • res = max(res, len);

#Code

#Solution #2 - DP - Java
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) {
if (s.isEmpty()) return 0;
int n = s.length();
char[] chs = s.toCharArray();
int[] dp = new int[n];
int res = 0;
for (int i = 1; i < n; i++) {
if (chs[i - 1] == '(' && chs[i] == ')') {
if (i == 1) dp[i] = 2;
else dp[i] = dp[i - 2] + 2;
} else if (chs[i - 1] == ')' && chs[i] == ')' && dp[i - 1] != 0 && i - dp[i - 1] - 1 >= 0 && chs[i - dp[i - 1] - 1] == '(') {
if (i - dp[i - 1] - 1 == 0) {
dp[i] = dp[i - 1] + 2;
} else {
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
#Solution #3 - Stack (index stack) - Java
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
class Solution {
public int longestValidParentheses(String s) {
if (s.isEmpty()) return 0;
int n = s.length();
Stack<Integer> stk = new Stack<>();
char[] chs = s.toCharArray();
int start = -1;
int res = 0;
for (int i = 0; i < n; i++) {
if (chs[i] == '(') {
stk.push(i);
} else {
if (stk.isEmpty()) {
start = i;
} else {
stk.pop();
if (stk.isEmpty()) {
res = Math.max(res, i - start);
} else {
res = Math.max(res, i - stk.peek());
}
}
}
}
return res;
}
}

Comments