二刷
Version #1 DP
95.24 %
当目前是')'的时候
找它前一个unmatched '(' -> prev -> i - 1 - dp[i - 1]
如果不存在,当前dp[i]就是0
如果存在,则该unmatched '(' 可以和current ')' match
dp[i] = dp[i - 1] + 2;
然而,unmatched '(' prev 之前可能存在valid substring
所以 dp[i] += dp[prev - 1];
Time O(n)
Space O(n)
class Solution {
public int longestValidParentheses(String s) {
int max = 0;
if (s == null || s.length() == 0) {
return max;
}
char[] chars = s.toCharArray();
// dp[i] -> longest length of valid substring end with index i
int[] dp = new int[s.length()];
// dp[0] = 0;
// "()(())"
for (int i = 1; i < chars.length; i++) {
if (chars[i] == '(') {
dp[i] = 0;
} else {
int prev = i - 1 - dp[i - 1];
if (prev >= 0 && chars[prev] == '(') { // match
dp[i] = dp[i - 1] + 2;
if (prev - 1 >= 0) {
dp[i] += dp[prev - 1];
}
}
max = Math.max(max, dp[i]);
}
}
return max;
}
}
Version #2 Stack
55.30 %
class Solution {
public int longestValidParentheses(String s) {
int max = 0;
if (s == null || s.length() == 0) {
return max;
}
char[] chars = s.toCharArray();
Stack<Integer> stack = new Stack<>();
int left = -1;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stack.push(i);
} else { // ')'
// left -> start of valid substring
if (stack.isEmpty()) {
left = i;
} else {
stack.pop(); //"...()"
if (stack.isEmpty()) {
max = Math.max(max, i - left);
} else {
// (())
max = Math.max(max, i - stack.peek());
}
}
}
}
return max;
}
}
一刷
Version #1 DP
dp定义为以当前index结尾的最长valid parentheses
85.21 %
如果是'(',则一定为0
如果是')' 则尝试着将它与latest没有匹配过的'('进行匹配
latest = currIndex - dp[curr - 1] - 1(检查几个可能越界的地方)
1.latest<=0 不存在 || latest == ')' 那么证明无法匹配
2. latest == '(' 正好可以跨越千山万水和当前的')' 匹配, 所以dp[curr] = dp[curr - 1] + 2
注意!这里还没有结束因为"()()"
有可能匹配之后正好与之前的接上,所以若prevIndex - 1 >= 0 的话,还要
dp[curr] += dp[prevIndex - 1
思路还是很难的
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) return 0;
//The longest valid parentheses ends with current index
int[] dp = new int[s.length()];
int max = 0;
char curr;
for (int i = 0; i < s.length(); i++) {
curr = s.charAt(i);
if (curr == '(') {
dp[i] = 0;
} else {//curr == ')'
if (i == 0) {
dp[i] = 0;
continue;
}
//The index of the latest invalid parentheses
int prevIndex = i - dp[i - 1] - 1;
if (prevIndex >= 0 && s.charAt(prevIndex) == '(') {
dp[i] = dp[i - 1] + 2;
if (prevIndex > 0) {
dp[i] = dp[i] + dp[prevIndex - 1];
}
} else {
dp[i] = 0;
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
No comments:
Post a Comment