LeetCode 0032 - Longest Valid Parentheses
# Hints
栈
DP
思维
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
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 "()`()"
# 题意
给定一个长为 的字符串 ,仅包含左右括号,求其最长合法子串的长度,即子串中的括号是合法匹配的。
# 题解
为便于描述,设 的下标为 。
方法1:栈
许多括号匹配问题都可以用栈解决。我们依次遍历整个字符串,遇到左括号则将当前下标入栈,遇到右括号则出栈,并进行一些细节处理。
在遇到右括号并出栈后,如果栈不为空则更新答案,如果栈为空,则将当前下标入栈,这样在将来出栈时便于更新答案。
一次遍历即可解决问题,时间复杂度为 。
细节问题:
- 初始化时记得将一个无用标记入栈,以防止 为右括号导致非法内存访问。
方法2:动态规划
考虑动态规划,设 表示以 结尾的最长合法子串的长度。
状态转移方程:
则 即为答案。
下面我们详细解释这个复杂的状态转移方程。
显然,当且仅当 时存在以 结尾的合法子串。
当 时,显然 和 可以就近配对,那么 可以与以 结尾的最长合法子串级联,因此 可由 转移。
当 时,可能不存在合法子串,也可能是形如 (((...)))
的嵌套匹配。不妨递归地想,如果在以 结尾的最长合法子串之前存在一个左括号,也就是 ,则可构成一个更长的合法的嵌套匹配。不要忘了还可以再前面的的最长合法子串级联,因此 可由 转移。
每个状态只有两个转移来源,因此总的时间复杂度为 。
方法3:思维
这个方法较难想到,我是从一个错误的思路出发才想到的。
如果你曾想过用双指针扫描解决本题,那么一定会想到初始令 ,然后令 递进并统计左右括号数,当右括号数多于左括号数时重置 。
但是容易发现,当左括号数多于右括号数时,例如对于 ((()()
,当 时,我们无法决定何时令 递进并寻找合法解,存在 种可能性,因为当 继续递进时可能发现新的右括号。这意味着单向扫描无法覆盖到所有答案,左括号数多于右括号数的情况无法处理,该方法似乎并不正确。
事实上,我们只需要倒着再做一遍,即可处理左括号数多于右括号数的情况,正反两遍扫描即可覆盖所有合法解。
此时可以发现, 指针的存在根本毫无意义,我们根本不需要双指针扫描,只需要直接遍历并统计左右括号数,当右括号数多于左括号数时重置统计值即可。
总的时间复杂度为 。该方法的时间常数比前两者更大,唯一的优势在于该方法仅需要 的额外空间。
# AC代码(栈)
class Solution {
public:
int longestValidParentheses(string s) {
// 初始化
int res = 0;
// 主循环
stack<int> stk;
stk.push(-1);
for (int i = 0; i < s.length(); i ++) {
if (s[i] == '(') {
// 入栈
stk.push(i);
} else {
// 出栈
stk.pop();
// 更新
if (stk.empty()) {
stk.push(i);
} else {
res = max(res, i - stk.top());
}
}
}
// 返回
return res;
}
};
# AC代码(动态规划)
class Solution {
public:
int longestValidParentheses(string s) {
// 初始化
int n = s.length();
int dp[n + 5];
memset(dp, 0, sizeof(dp));
// 递推
for (int i = 1; i < n; i ++) {
if (s[i] == ')') {
if (s[i - 1] == '(') {
dp[i] = get_value(dp, i - 2) + 2;
} else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
dp[i] = get_value(dp, i - dp[i - 1] - 2) + dp[i - 1] + 2;
}
}
}
// 求最大值
int res = 0;
for (int i = 0; i < n; i ++) {
res = max(res, dp[i]);
}
// 返回
return res;
}
// 处理向下越界
inline int get_value(int dp[], int index) {
return (index >= 0 ? dp[index] : 0);
}
};
# AC代码(思维)
class Solution {
public:
int longestValidParentheses(string s) {
// 初始化
int res = 0;
// 正向求解
res = max(res, solve(s, '('));
// 反向求解
reverse(s.begin(), s.end());
res = max(res, solve(s, ')'));
// 返回
return res;
}
// 解决
int solve(const string & s, const char lch) {
// 初始化
int res = 0;
// 主循环
int lcnt = 0, rcnt = 0;
for (int i = 0; i < s.length(); i ++) {
// 统计
if (s[i] == lch) {
lcnt ++;
} else {
rcnt ++;
}
// 更新答案
if (lcnt == rcnt) {
res = max(res, lcnt + rcnt);
}
// 清空
if (lcnt < rcnt) {
lcnt = 0;
rcnt = 0;
}
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01