Content
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = "(()" Output: 2 Explanation: The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()".
Example 3:
Input: s = "" Output: 0
Constraints:
0 <= s.length <= 3 * 104s[i]is'(', or')'.
Related Topics
Solution
1. 动态规划
Java
class Solution {
public int longestValidParentheses(String s) {
// dp[i]表示字符串s中以i下标结尾的最长有效括号串的长度。
int n = s.length();
if (n < 2) {
return 0;
}
int[] dp = new int[n];
if (s.charAt(0) == '(' && s.charAt(1) == ')') {
dp[1] = 2;
}
for (int i = 2; i < n; i++) {
char c0 = s.charAt(i - 1);
char c1 = s.charAt(i);
if (c1 == ')') {
if (c0 == '(') {
dp[i] = dp[i - 2] + 2;
} else if (dp[i - 1] > 0) {
// i0表示s中以（i - 1）下标结尾的最长有效括号串前一个下标
int i0 = i - 1 - dp[i - 1];
if (i0 >= 0) {
char c2 = s.charAt(i0);
if (c2 == '(') {
dp[i] = (i0 > 0 ? dp[i0 - 1] : 0) + dp[i - 1] + 2;
}
}
}
}
}
int longest = 0;
for (int j = 0; j < n; j++) {
longest = Math.max(longest, dp[j]);
}
return longest;
}
}
- longest-valid-parentheses parentheses LeetCode longest validlongest-valid-parentheses parentheses leetcode longest-valid-parentheses parentheses longest valid 32 parentheses valid substring leetcode balanced longest leetcode longest binary zigzag consecutive leetcode sequence longest leetcode validate binary nodes leetcode number clock valid palindrome leetcode valid 2330