32. Longest Valid Parentheses

二刷
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;
    }
}