符合直觉的做法是：分别计算以 i 开头的 最长有效括号（i 从 0 到 n - 1·），从中取出最大的即可。
代码
代码支持： Python
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
ans = 0
def validCnt(start):
# cnt 为 ) 的数量减去 ( 的数量
cnt = 0
ans = 0
for i in range(start, n):
if s[i] == '(':
cnt += 1
if s[i] == ')':
cnt -= 1
if cnt < 0:
return i - start
if cnt == 0:
ans = max(ans, i - start + 1)
return ans
for i in range(n):
ans = max(ans, validCnt(i))
return ans
// 用栈来解
var longestValidParentheses = function (s) {
let stack = new Array();
let longest = 0;
stack.push(-1);
for (let i = 0; i < s.length; i++) {
if (s[i] === "(") {
stack.push(i);
} else {
stack.pop();
if (stack.length === 0) {
stack.push(i);
} else {
longest = Math.max(longest, i - stack[stack.length - 1]);
}
}
}
return longest;
};
Python Code:
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
res = 0
stack = [-1]
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
res = max(res, i - stack[-1])
return res
CPP Code:
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> st;
st.push(-1);
int ans = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == ')' && st.top() != -1 && s[st.top()] == '(') {
st.pop();
ans = max(ans, i - st.top());
} else st.push(i);
}
return ans;
}
};
复杂度分析
时间复杂度：$O(N)$
空间复杂度：$O(N)$
O(1) 空间
思路
我们可以采用解法一中的计数方法。
从左到右遍历一次，并分别记录左右括号的数量 left 和 right。
如果 right > left ，说明截止上次可以匹配的点到当前点这一段无法匹配，重置 left 和 right 为 0
如果 right == left, 此时可以匹配，此时有效括号长度为 left + right，我们获得一个局部最优解。如果其比全局最优解大，我们更新全局最优解
public class Solution {
public int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, left + right);
}
if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, left + right);
}
if (left > right) {
left = right = 0;
}
}
return maxlength;
}
}
Python3 Code:
class Solution:
def longestValidParentheses(self, s: str) -> int:
ans = l = r = 0
for c in s:
if c == '(':
l += 1
else:
r += 1
if l == r:
ans = max(ans, l + r)
if r > l:
l = r = 0
l = r = 0
for c in s[::-1]:
if c == '(':
l += 1
else:
r += 1
if l == r:
ans = max(ans, l + r)
if r < l:
l = r = 0
return ans
CPP Code:
class Solution {
public:
int longestValidParentheses(string s) {
int left = 0, right = 0, ans = 0, N = s.size();
for (int i = 0; i < N; ++i) {
left += s[i] == '(';
right += s[i] == ')';
if (left == right) ans = max(ans, left + right);
else if (right > left) left = right = 0;
}
left = 0, right = 0;
for (int i = N - 1; i >= 0; --i) {
left += s[i] == '(';
right += s[i] == ')';
if (left == right) ans = max(ans, left + right);
else if (left > right) left = right = 0;
}
return ans;
}
};
动态规划
思路
所有的动态规划问题, 首先需要解决的就是如何寻找合适的子问题. 该题需要我们找到最长的有效括号对, 我们首先想到的就是定义dp[i]为前 i 个字符串的最长有效括号对长度, 但是随后我们会发现, 这样的定义, 我们无法找到 dp[i]和 dp[i-1]的任何关系. 所以, 我们需要重新找一个新的定义: 定义dp[i]为以第 i 个字符结尾的最长有效括号对长度. 然后, 我们通过下面这个例子找一下 dp[i]和 dp[i-1]之间的关系.
s = '(())())'
从上面的例子我们可以观察出一下几点结论(描述中 i 为图中的 dp 数组的下标, 对应 s 的下标应为 i-1, 第 i 个字符的 i 从 1 开始).
base case: 空字符串的最长有效括号对长度肯定为 0, 即: dp[0] = 0;
s 的第1个字符结尾的最长有效括号对长度为 0, s 的第2个字符结尾的最长有效括号对长度也为 0, 这个时候我们可以得出结论: 最长有效括号对不可能以'('结尾, 即: dp[1] = d[2] = 0;
