最长有效括号（Longest Valid Parentheses）-leetcode32

题目描述

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例

输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()”

输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

思路

代码

class Solution { public: int longestValidParentheses(string s) { int n = s.length();//数组长度 vector<int> dp(n,0);//建立数组并 初始化为0 int max = 0; //求max值 for(int i = 1;i < n;i++) { if(s[i] == ')') { // 只看）便可得知答案 if(s[i - 1] == '(') {// 当为 1形 时候 if(i - 2 >= 0) { //考虑前方有效括号对 dp[i] = 2 + dp[i-2]; } else { dp[i] = 2; } } else if(i-dp[i-1] > 0 && s[i-dp[i-1]-1] == '('){ //判断当前括号是否有效 if(i - dp[i - 1] - 2 >= 0) { // 考虑之前有效括号对 dp[i] = 2 + dp[i-1] + dp[i-dp[i-1]-2]; } else { //之前没有有效括号对 dp[i] = 2 + dp[i-1]; } } } if(dp[i] > max) { max = dp[i]; } } return max; } };

总结

本题还可以使用 栈 来完成。这是我写的第一个hard题，真是有够难的。动态规划类的题目，首先考虑好状态转换方程，其次再考虑边界条件。