首页 > 代码库 > 【leetcode】Longest Valid Parentheses
【leetcode】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.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
设dp[i]表示从s[i]开始（包括s[i]），到达s[n-1]时，最长的有效括号对的长度。
如果s[i]==‘(‘
我们需要检查j=dp[i+1]+i+1对应的s[j]位置的括号是否为")"，如果s[j]为‘)‘则说明又组成了一对括号
故此时dp[i]=dp[i+1]+2
于此同时，我们还需要继续考虑dp[j+1]的值，如果j+1没有超出范围，则dp[i]=dp[i+1]+2+dp[j+1]
其他情况dp[i]=0;
1 class Solution { 2 public: 3 int longestValidParentheses(string s) { 4 int n=s.length(); 5 if(n==0) return 0; 6 7 int *dp=new int[n]; 8 dp[n-1]=0; 9 10 int result=0;11 for(int i=n-2;i>=0;i--)12 {13 if(s[i]==‘(‘)14 {15 int j=dp[i+1]+i+1;16 17 if(s[j]==‘)‘)18 {19 dp[i]=dp[i+1]+2;20 if(j<n-1) dp[i]+=dp[j+1];21 }22 else23 {24 dp[i]=0;25 }26 27 if(dp[i]>result)28 {29 result=dp[i];30 }31 }32 else33 {34 dp[i]=0;35 }36 }37 delete [] dp;38 return result;39 }40 };
【leetcode】Longest Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。