My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() <= 1)
return 0;
int len = s.length();
int max = 0;
int[] dp = new int[len];
for (int i = len - 2; i >= 0; i--) {
int j = i + dp[i + 1] + 1;
if (j < len && s.charAt(i) == '(' && s.charAt(j) == ')')
dp[i] = dp[i + 1] + 2;
else
continue;
j = i + dp[i];
if (j < len && dp[j] != 0) {
dp[i] += dp[j];
}
max = Math.max(max, dp[i]);
}
return max;
}
}
这道题目我没有做出来。应该说，我做出来了，但是超时了。
我也想到了用dp，但是用的是二维数组。后来看了提示，想到用一维数组，但是一个关键我忘记了。
当dp[i] 成功赋值后，即dp[i] == '(' && dp[j] == ')', 需要观察观察，dp[i + dp[i]] 是否为0，如果不是，需要合并。
还有个做法是stack的。不是很难。具体就不写了。
一个早上，洗了个澡，洗了衣服。投了两个实习。马上要上课了。
太忙了，但感觉什么都没收获。
参考网页：
DP:
http://blog.csdn.net/abcbc/article/details/8826782
Stack:
http://www.programcreek.com/2014/06/leetcode-longest-valid-parentheses-java/
Anyway, Good luck, Richardo!
Stack 做法：
My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0)
return 0;
Stack<int[]> ss = new Stack<int[]>();
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (curr == '(') {
int[] temp = {i, 0};
ss.push(temp);
}
else {
if (ss.isEmpty() || ss.peek()[1] == 1) {
int[] temp = {i, 1};
ss.push(temp);
}
else {
ss.pop();
if (ss.isEmpty()) {
maxLen = Math.max(maxLen, i + 1);
}
else {
maxLen = Math.max(maxLen, i - ss.peek()[0]);
}
}
}
}
return maxLen;
}
}
Anyway, Good luck, Richardo!
首先写一个超时的二维DP算法。
My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[][] dp = new int[len][len];
int max = 0;
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
char curr = s.charAt(j);
int end = i;
if (curr == ')') {
if (j > 0 && dp[i][j - 1] > 0) {
dp[i][j] = dp[i][j - 1] - 1;
}
else {
dp[i][j] = -1;
}
}
else {
if (j > 0 && dp[i][j - 1] < 0) {
dp[i][j] = -1;
}
else if (j > i) {
dp[i][j] = dp[i][j - 1] + 1;
}
else {
dp[i][j] = 1;
}
}
if (dp[i][j] == 0) {
end = Math.max(end, j);
max = Math.max(max, end - i + 1);
}
}
}
return max;
}
}
这么做的原因，在于。
我先用brute force进行解答，然后发现，重复操作的地方，然后再用DP cache
从 O(n ^ 3) -> O(n ^ 2)
但是仍然超时, 仍需要优化。
DP solution:
My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[] dp = new int[len];
int max = 0;
for (int i = dp.length - 2; i >= 0; i--) {
char curr = s.charAt(i);
if (curr == ')') {
dp[i] = 0;
}
else {
int j = i + 1 + dp[i + 1];
if (j < dp.length) {
if (s.charAt(j) == ')') {
dp[i] = j - i + 1;
}
else {
continue;
}
}
j = i + dp[i];
if (j < dp.length) {
dp[i] = dp[i] + dp[j];
}
max = Math.max(max, dp[i]);
}
}
return max;
}
}
还是看的以前的思路。
两个注意点；
- 从倒数第二位开始后退遍历就行了。
- 跳跃时，不用一直跳到最后。跳一次。然后如果是 ')'
就更新d[[i]
然后如果 dp[j + 1] > 0,
再次更新 dp[i]
测试程序有时候可以过，有时候时间超了。我想本身的代码应该问题不大，就是 O(n)的复杂度。
下面开始想一下 Stack 的做法：
My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Stack<Integer> st = new Stack<Integer>();
int left = -1;
int max = 0;
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (curr == '(') {
st.push(i);
}
else {
if (st.isEmpty()) {
left = i;
}
else {
st.pop();
if (st.isEmpty()) {
max = Math.max(max, i - left);
}
else {
max = Math.max(max, i - st.peek());
}
}
}
}
return max;
}
}
reference:
https://discuss.leetcode.com/topic/7234/simple-java-solution-o-n-time-one-stack
只是不知道为什么，最后一个case，总是 time limited。我这个明明是 O(n) 啊。
不管了。
具体思想就是，
stack 里面只存 ' ( '
栈里面存的都是 index
当碰到 ( 时，就直接push
当碰到 ) 时，
如果此时栈为空了，就代表上一层的valid parenthesis 已经结束了，那么移动left指针，只想当前 ) index
如果未空，那么上一层的 valid parenthesis 并没有结束，先将这个匹配的 ( 弹出。然后计算下该段 valid parenthesis 的有效长度
此时又有两种情况。
如果栈空了，表示这一层的valid parenthesis 结束了。那么
[left, i]
如果栈未空，那么该层还没有彻底结束。那么起始位置应该是 s.peek()
[s.peek(), i]
因为在 [s.pop(), i] 之前可能还存在其他并且的有效字段，只不过已经提前弹出去了，所以算最大长度时，要一起考虑进去。
差不多就这样了。
Anyway, Good luck, Richardo! -- 08/18/2016
发现之前的理解还是肤浅了，只记得有跳跃的过程，忘记了还有合并的过程。
1 . 跳跃，将自己的有限范围找出来
2 . merge, 将其他和自己相邻的有限部分merge
求最大值。
同样的思路并不适用于 longest palindrome.
因为panlindrome一个字母也可以是一个panlidrome
Stack 的做法也是只理解了意思，自己敲还是没写出来。
最大的特点是，栈里面只放 '('
好处是，当我碰到 ')'时，
我不用判断栈顶元素是什么，因为他一定是 '('
我将它弹出来，看栈是否为空。
所以这里，我需要一个变量来暂存每一块valid区域的最左边界的再左边一个点。
当栈空的时候，len = i - left;
否则， len = i - st.peek();
max = Math.max(max, len);
Anyway, Good luck, Richardo! -- 09/18/2016
