Longest Valid Parentheses(动态规划)

Longest Valid Parentheses更多技术博客 http://vilins.top/题目Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.Example 1:Input: “(()”Output: 2Explanation: The longest valid parentheses substring is “()”Example 2:Input: “)()())”Output: 4Explanation: The longest valid parentheses substring is “()()”分析在这里我们用一个longest_curr数组去保存当前下标前连续匹配的括号的数量注意这里是连续出现的括号。接下来我们需要找出状态转移方程当字符串的字符为’)‘时可能意味着状态的改变所以我们的判断条件是在’)‘时进行的。具体来说在下标i之前的longest_curr值都已经被求出来了那么对于下标为并且是’)的字符有如下状态转移方程longest_curr[i] longest_curr[i - longest_curr[i-1] - 2] 2 longest_curr[i-1];longest_curr[i - longest_curr[i-1] - 2]是指在这个整体匹配之前已经匹配的字符数量longest_curr[i-1]指存在这样的情况“()(())longest_curr[i-1]指计算这个符合中间的这两个。最后需要考虑的一点就是下标的界限问题。源码class Solution { public: int longestValidParentheses(string s) { int size s.size(); int max_num 0; vectorint longest_curr(size, 0); if(s.size() 1) { return 0; } for(int i 1; i size; i) { if(s[i] ) ((i - longest_curr[i-1] - 1) 0) s[i - longest_curr[i-1] - 1] () { if(i - longest_curr[i-1] - 2 0) { longest_curr[i] longest_curr[i - longest_curr[i-1] - 2] 2 longest_curr[i-1]; } else { longest_curr[i] 2 longest_curr[i-1]; } max_num max(max_num, longest_curr[i]); } } return max_num; } };更多技术博客 http://vilins.top/