# 引言
题目链接：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 | |
} |
