美文网首页
leetcode--32--最长有效括号

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

作者: minningl | 来源:发表于2021-06-18 00:55 被阅读0次

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

示例 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();

    }
}

相关文章

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

    题目:给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例 1: 输...

  • 最长有效括号

    题目来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/long...

  • 最长有效括号

    //给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。//输入:s = ...

  • 最长有效括号

    难点在于()()如何匹配前面的连续(),还有(())如何处理 举例:s[i-2]==")" ()([)]=>dp[...

  • 最长有效括号

    32. 最长有效括号 题目: 给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串...

  • LeetCode-32-最长有效括号

    LeetCode-32-最长有效括号 题目 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的...

  • LeeCode刷题笔记4:最长有效括号

    @[TOC](最长有效括号) 题目描述 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串...

  • 32. 最长有效括号

    32. 最长有效括号 视频讲解挺好的

  • leetcode 32 最长有效括号

    32. 最长有效括号 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1...

  • 最长的有效括号

    题目描述:给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度. 示例:输入: ")(...

网友评论

      本文标题:leetcode--32--最长有效括号

      本文链接:https://www.haomeiwen.com/subject/panhyltx.html