leetcode--32--最长有效括号

题目：
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：

输入：s = ""
输出：0

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

链接：https://leetcode-cn.com/problems/longest-valid-parentheses

Python代码:

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        dp = [0]*len(s)

        for i in range(len(s)):
            # i 对于的值是 i-dp[i-1]-1
            if s[i]==')' and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=='(':
                dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
        return max(dp)

Java代码:

import java.util.Collections;
import java.util.Vector;

class Solution {
    public int longestValidParentheses(String s) {
        if(s.length()==0){
            return 0;
        }
        int[] dp = new int[s.length()];
        for (int i=1; i<s.length(); i++){
            if(s.charAt(i)==')' && (i-dp[i-1]-1)>=0 && s.charAt(i-dp[i-1]-1)=='('){
                if (i-dp[i-1]-2>=0){
                    dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2;
                }else{
                    dp[i] = dp[i-1] + 2;
                }
            }
        }

        return Arrays.stream(dp).max().getAsInt();

    }
}