引言
题目链接：https://leetcode.com/problems/longest-valid-parentheses/
题目大意
给定一个只包含字符'('和')'的字符串，找到最长的有效（括号配对）括号子字符串的长度。
- Example
|
1 2 3 4 5 6 7 |
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] 对应索引是否为 '(' 即可
于是有如下状态转移方程
|
1 2 3 4 |
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++版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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 } |
