LeetCode 笔记系列八 Longest Valid Parentheses [lich你又想多了]
题目: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.
拿到题目,哎呀,这不是典型的动态规划嘛,然后刷刷开始coding。这道题确实可以用动态规划,但是复杂度就上去了,事实证明也没法通过大集合的测试。不过还是可以当一个DP的练习。如果你比较忙,直接看解法二吧。
用longestValid[i][j]表示从S串中的字符i到j的最长well-formed表达式的长度;isValid[i][j]表示从i到j是否是一个valid的表达式。
如何判断longestValid[i][j]的取值呢?有下面几种情况:
假定有一个maxlength变量。
1. 如果i='(' 并且 j=')',
a. 如果j = i+1,那这是一个valid的表达式;
b. 如果isValid[i+1][j-1]为真,那这也是一个valid表达式;
c. 对所有在i到j之间的k,如果isValid[i,k]&&isValid[k+1,j]为真,那么这是一个valid表达式,这三种情况maxlength都是i到j的距离;
d.其他情况,maxlength = longestValid[i][j-1]和 longestValid[i+1][j]比较大的那个。
2. 如果i='(' 并且 j='(', maxlength等于longestValid[i][j-1]。
3. 如果i=')' 并且 j=')', maxlength等于longestValid[i+1][j]。
4. 如果i=')‘ 并且 j='(', maxlength等于longestValid[i-1][j-1].
判断完成后,longestValid[i][j]赋值于maxlength。
下面是代码,是不是很复杂很想给博客君一巴掌。
解法一:
private static int longestValidParentheses(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(s.length() == 0) return 0;
boolean[][] isValid = new boolean[s.length()][];//isValid[i][j] is true when from i to j, this is a valid parentheses expression
int[][] longestValid = new int[s.length()][];//the longest length of valid expression between i and j
for(int i = 0; i < s.length();i++){
isValid[i] = new boolean[s.length()];
longestValid[i] = new int[s.length()];
}
for(int j = 1; j < s.length();j++){
for(int i = j - 1; i >=0;i--){
int left = s.charAt(i);
int right = s.charAt(j);
int maxLength = 0;
if(left == '(' && right ==')'){
if(i + 1 == j) {
isValid[i][j] = true;
if(maxLength < 2) maxLength = 2;
}else {
if(isValid[i+1][j-1]){
isValid[i][j] = true;
if(maxLength < j - i + 1) maxLength = j - i + 1;
}else if(isValid[i][i+1] && isValid[j-1][j] &&
(isValid[i + 2][j - 2] || j - i == 3)){
isValid[i][j]=true;
if(maxLength < j - i + 1) maxLength = j - i + 1;
}else {
maxLength = Math.max(longestValid[i][j-1], longestValid[i+1][j]);
for(int k = i + 1; k < j;k++){
if(isValid[i][k] && isValid[k + 1][j]) {
maxLength = j - i + 1;
isValid[i][j]=true;
break;
}
}
}
}
}else {
if(left == '(' && right == '('
&& longestValid[i][j-1] > maxLength) maxLength = longestValid[i][j-1];
if(left == ')' && right == ')'
&& longestValid[i+1][j] > maxLength)maxLength = longestValid[i+1][j];
if(left ==')' && right == '('
&& longestValid[i+1][j-1] > maxLength){
maxLength = longestValid[i+1][j-1];
}
}
longestValid[i][j] = maxLength;
}
}
return longestValid[0][s.length()-1];
}
plus,这是O(n3)的。。。。“该吃药了。。亲”。如期望的,该解法在大集合的时候超时。
解法二:来自leetcode讨论组的写法。本来人有O(n)的解法,被楼主活生生地卖弄成了O(n3)。楼主真想挖个坑把自己埋了!!!
大家首先看,这个解法里面的stack,不是用来存左右括号的。人是来存左括号的index。本来么,右括号也不用存。遍历S。遇到'(',放入lefts。如果遇到')',如果lefts是空,说明这是一个无法匹配的')',记录下last。last里面存放的其实是最后一个无法匹配的')'。为啥要保存这个值呢?主要是为了计算后面完整的表达式的长度。可以这样理解: “所有无法匹配的')'”的index其实都是各个group的分界点。
public static int longestValidParentheses2(String s) {
int maxLen = 0, last = -1;
Stack<Integer> lefts = new Stack<Integer>();
for (int i=0; i<s.length(); ++i) {
if (s.charAt(i)=='(') {
lefts.push(i);
} else {
if (lefts.isEmpty()) {
// no matching left
last = i;
} else {
// find a matching pair
lefts.pop();
if (lefts.isEmpty()) {//有一个完整的valid的group。计算该group的长度
maxLen = Math.max(maxLen, i-last);
} else {
//栈内还有‘(',一个最外层完整的group还没有匹配完成,
//但是通过查询下一个即将匹配还未匹配的"("的index来更新maxLen。
maxLen = Math.max(maxLen, i-lefts.peek());
}
}
}
}
return maxLen;
}
总结下:
DP不是万能的。注意发现问题的本质。不过这个确实要靠足够的练习。解法二的代码确实很简洁,但是并不是人人都能想到的。
最新文章
- Struts 笔记 内部资料 请勿转载 谢谢合作
- vs2013 支持C#6.0 Install-Package Microsoft.Net.Compilers
- C++ stringstream
- eclipse 导入web项目后,线程假死
- C++ 封装互斥对象
- asp.net 捕获全局未处理异常的几种方法
- onSaveInstanceState和onRestoreInstanceState
- Objective-C中的Block
- HDU 4800/zoj 3735 Josephina and RPG 2013 长沙现场赛J题
- COJN 0575 800601滑雪
- 射频识别技术漫谈(15)——Mifare1的安全性及7字节序列号M1卡
- 一种基于路网图层的GPS轨迹优化方案
- 圆形的ImageView
- 05 利用Appliction 传值Activity
- sass基本用法
- 【Mac进销存管理软件】Daily Sales Pro Mac
- C# winform 打开主界面并关闭登录界面
- 1.1.17 Word在表格中插入竖排文字,显示一半
- [CocoaPods]CocoaPods安装详解
- “IT学子成长指导”专栏及文章目录 —贺利坚
热门文章
- Hexo快速搭建静态博客并实现远程VPS自动部署
- 数据库连接 UnicodeEncodeError: &#39;latin-1&#39; codec can&#39;t encode character u&#39;\u4eac&#39; in position 0: ordinal not in range(256),UnicodeEncodeError: &#39;latin-1&#39; codec can&#39;t encode character
- intelliJ IDEA 配置MySQL数据库 详解
- spring in action小结2
- web.xml文件书写规则
- blender, 同时选择多个顶点
- Mybatis(一):MyBatis配置文件config.xml详解
- Murano环境搭建、使用介绍和思考
- plink参数说明
- Ubuntu 15.04 开启远程桌面