[leetcode]Longest Valid Parentheses

qujian 发布于2019-08-14 16:53 / 1924人阅读

摘要：在问题中，我们可以用来检验括号对，也可以通过来检验。遇到就加一，遇到就减一。找到一对括号就在最终结果上加。我们用来表示当前位置的最长括号。括号之间的关系有两种，包含和相离。

Longest Valid Parentheses

Given a string containing just the characters "(" and ")", find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2. 
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

在valid parentheses问题中，我们可以用stack来检验括号对，也可以通过count来检验。遇到"("就加一，遇到")"就减一。找到一对括号就在最终结果上加2。
我们用value[i]来表示当前位置的最长括号。
括号之间的关系有两种，包含：() or (()) or ((()))和相离()() or ()(())。

public class Solution {
    public int longestValidParentheses(String s) {
        char[] chs = s.toCharArray();
        int[] value = new int[chs.length];
        int open = 0;
        int max = 0;
        
        for(int i=0; i < chs.length; i++){
            if(chs[i] == "(") open++;
            if(chs[i] == ")" && open > 0) {
                //包含关系，通过最近的括号长度来改变。
                // ()    dp[1] = dp[0] +2
                // (())  dp[2] = dp[1] +2 =2,  dp[3] = dp[2] +2 = 4
                value[i] = 2 + value[i-1];
                //相离关系，通过相离的括号长度来改变。
                // ()()  dp[3] = dp[3] + dp[1] = 2 + 2 = 4
                if(i-value[i] > 0){
                    value[i] += value[i-value[i]];
                }
                open--;
            }
            if(value[i] > max) max = value[i];
        }
        
        return max;
    }
}

海外云主机私有云 Parentheses Longest Leetcod Valid

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

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

[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] 32. Longest Valid Parentheses

Problem Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: (()Output: 2Explanation: The longest valid pa...

Flink_China 2019-08-19 11:14 评论0 收藏0
leetcode32 Longest Valid Parentheses 最长括号组的长度

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

happyhuangjinjin 2019-08-14 18:13 评论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