[LeetCode] 32. Longest Valid Parentheses

Flink_China 发布于2019-08-19 11:14 / 1494人阅读

Problem

Given a string containing just the characters "(" and ")", find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Solution DP

class Solution {
    public int longestValidParentheses(String s) {
        //()((()))
        //()()()()
        int max = 0, left = 0;
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == "(") left++;
            else {
                if (left != 0) {
                    dp[i] = dp[i-1]+2;
                    if (i-dp[i] >= 0) dp[i] += dp[i-dp[i]];
                    max = Math.max(max, dp[i]);
                    left--;
                }
            }
        }
        return max;
    }
}

Stack

class Solution {
    public int longestValidParentheses(String s) {
        //stack to store index
        Stack stack = new Stack<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ")" && !stack.isEmpty() && s.charAt(stack.peek()) == "(") {
                //remove this pair
                stack.pop();
                
                //update the length of this pair
                //
                //if starts with )
                if (!stack.isEmpty()) max = Math.max(max, i-stack.peek());
                //if starts with (
                else max = i+1;
            } else {
                stack.push(i);
            }
        }
        return max;
    }
}

海外云主机 GPU服务器 Parentheses Longest LeetCode Valid

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77248.html

leetcode32 Longest Valid Parentheses 最长括号组的长度

摘要：题目要求原题地址一个括号序列，求出其中成对括号的最大长度思路一使用堆栈这题可以参考我的另一篇博客这篇博客讲解了如何用堆栈判断括号序列是否可以成对。我们可以将堆栈的思路延续到这里。在这里需要先遍历一遍字符串，再遍历一下非空的堆栈。题目要求原题地址：https://leetcode.com/problems... Given a string containing just the c...

happyhuangjinjin 2019-08-14 18:13 评论0 收藏0
[leetcode]Longest Valid Parentheses

摘要：在问题中，我们可以用来检验括号对，也可以通过来检验。遇到就加一，遇到就减一。找到一对括号就在最终结果上加。我们用来表示当前位置的最长括号。括号之间的关系有两种，包含和相离。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the lon...

qujian 2019-08-14 16:53 评论0 收藏0
[Leetcode] Longest Valid Parentheses 最长有效括号对

摘要：假设是从下标开始到字符串结尾最长括号对长度，是字符串下标为的括号。如果所有符号都是，说明是有效的。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses...

everfight 2019-08-14 16:11 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0