Longest Valid Parentheses(动态规划)

Longest Valid Parentheses

题目

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

Example 1:

Input: “(()”

Output: 2

Explanation: The longest valid parentheses substring is “()”

Example 2:

Input: “)()())”

Output: 4

Explanation: 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;
    	vector<int> 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;
     }
};
           

更多技术博客：https://vilin.club/