leetcode打卡 Longest Valid Parentheses

题目

Given a string containing just the characters'(' and')', find the length of the longest valid (well-formed) parentheses substring.

大意就是：给定一个只包含 '('和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 示例1：

Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"

示例2

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"

注：类似(())也是有效匹配，长度为4

分析

该题在leetcode动态规划的分类下，所以我们可以使用动态规划来解决该问题。我们可以使用一个数组arr来记录字符串s在下标i的位置时，其有效长度为多少。

当s[i] == '('， arr[i] = 0当s[i] == ')'，需要分两种情况来讨论 当s[i-1]=='('时，很明显arr[i] = arr[i-2] + 2，因为此时有效子串的长度多增加了一对括号()，即有效子串长度+2当s[i-1]==')'时。考虑这样的情况，假设sub = "((......))"是给定字字符串的一部分，且为有效子串。那么arr[i]的值为sub字符串的长度+sub前一个下标(记为j)的对应的arr的值，即arr[i] = len(sub) + arr[j]。那么sub的长度和j该如何计算呢？我们仔细观察一下，因为sub是有效子串，所以len(sub) = arr[i-1] + 2，j = i - arr[i-1] - 2。(这样强行解释一波不知道行不行得通

代码

class Solution { public: int longestValidParentheses(string s) { if(s.size() == 0) { return 0; } int max = 0; int arr[s.size()] = {0}; for(int i = 0; i < s.size(); ++i) { if(s[i] == ')' && i > 0) { if(s[i-1] == '(') { arr[i] = i >= 2 ? arr[i-2] + 2 : 2; } else if(i - arr[i - 1] > 0 && s[i - arr[i - 1] - 1] == '(') { arr[i] = arr[i-1] + (i - arr[i-1] -2 >= 0 ? arr[i - arr[i-1] -2]:0) + 2; } } if(arr[i] > max) { max = arr[i]; } } return max; } };