题解 | #最长的括号子串#

最长的括号子串

http://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad

import java.util.*; public class Solution { /** * @param s string字符串 * @return int整型 */ public int longestValidParentheses (String s) { //最长的括号子串,使用栈,左括号入栈,遇到右半括号出栈并长度加2,没有左半括号就截止 //注意,如果入栈数目多于右半括号,那么就不是连续的,必须右半括号完全与左半括号匹配才能计数 if(s.isEmpty() || s.length()==0) return 0; int[] dp = new int[s.length()]; //动态规划数组 int len = 0; for(int i=1; i<s.length(); i++){ if(s.charAt(i) == ')'){ if(s.charAt(i-1) == '(') dp[i] = (i >= 2 ? dp[i-2] : 0) + 2; else if(i - dp[i-1] > 0 && s.charAt(i-dp[i-1] - 1) == '('){ dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2; } } len = len < dp[i] ? dp[i] : len; } return len; } }

我居南半坡 文章被收录于专栏

多刷题,积蓄力量,欢迎讨论

全部评论

相关推荐

Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-04 15:20
牛客61197583...:看到室友一个个没怎么学通过关系直接入职或者接到面试,真的很难受。八股不知道背了多少遍,hot100也刷了1.5遍了,但就是没有面试的机会,唉
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务