# 引言
题目链接：https://leetcode.com/problems/longest-valid-parentheses/
# 题目大意
给定一个只包含字符'('和')'的字符串, 找到最长的有效(括号配对)括号子字符串的长度。
- Example
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"# 题解
明确一个要点, 一个匹配的字符串一定是以 ')' 结尾
假设 dp[i] 表示从字符串开头以第i位结尾的子字符串的最大匹配长度, 每次读取到为 ')' 的字符串只需要判断第 i-1-dp[i-1] 对应索引是否为 '(' 即可
于是有如下状态转移方程
dp[i] = dp[i-1] + 2 ( s[i] == ')' && s[i-1-dp[i-1]]=='(' )
dp[i] += dp[i - dp[i]];
递归边界dp[0] = 0再进行dp时注意维护最大值即可, 为了避免越界情况, 博主采取在目标字符串头部添加一个无效字符。
# 复杂度
时间复杂度 O(n)
空间复杂度 O(n)
# AC代码
c++版本
class Solution
{
public:
int longestValidParentheses(string s)
{
int ans = 0;
string prefixs = "#" + s;
vector<int> dp(prefixs.length(), 0);
for (int i = 1; i < prefixs.length(); ++i)
{
// 更新
if (prefixs[i] == ')')
{
if (prefixs[i - dp[i - 1] - 1] == '(')
{
dp[i] = dp[i - 1] + 2;
}
dp[i] += dp[i - dp[i]];
}
ans = max(ans, dp[i]);
}
return ans;
}
};go版本
func longestValidParentheses(s string) int {
prefixs := strings.Join([]string{"#", s}, "")
ans, lens, dp := 0, len(prefixs), make([]int, len(prefixs))
for i := 1; i < lens; i++ {
if prefixs[i] == ')' {
if prefixs[i-1-dp[i-1]] == '(' {
dp[i] = dp[i-1] + 2
}
dp[i] += dp[i-dp[i]]
}
if ans < dp[i] {
ans = dp[i]
}
}
return ans
}
有什么想法，欢迎留下评论。