[Leetcode] Longest Valid Parentheses 最长有效括号对

everfight 发布于2019-08-14 16:11 / 2727人阅读

摘要：假设是从下标开始到字符串结尾最长括号对长度，是字符串下标为的括号。如果所有符号都是，说明是有效的。

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.

栈法 Stack 复杂度

时间 O(N) 空间 O(N)

思路

用Stack的方法本质上和Valid Parentheses是一样的，一个右括号能消去Stack顶上的一个左括号。不同的是，为了能够计算括号对的长度我们还需要记录括号们的下标。这样在弹出一个左括号后，我们可以根据当前坐标减去栈中上一个（也就是Pop过后的Top元素）的坐标来得到该有效括号对的长度。

代码

public class Solution {
    public int longestValidParentheses(String s) {
        Stack stk = new Stack();
        int maxLen = 0;
        for(int i = 0; i < s.length(); i++){
            //遇到左括号，将其push进栈
            if(s.charAt(i)=="("){
                stk.push(new Parenthese(i, "("));
            } else {
           //遇到右括号，分类讨论
               //如果当前栈顶是左括号，则消去并计算长度
                if(!stk.isEmpty() && stk.peek().symb=="("){
                    int curLen = 0;
                    stk.pop();
                    if(stk.isEmpty()){
                        curLen = i + 1;
                    } else {
                        curLen = i - stk.peek().indx;
                    }
                    maxLen = Math.max(maxLen, curLen);
                } else {
               //如果栈顶是右括号或者是空栈，则将右括号也push进栈，它的坐标将方便之后计算长度
                    stk.push(new Parenthese(i, ")"));
                }
            }
        }
        return maxLen;
    }
    
    public class Parenthese {
        int indx;
        char symb;
        public Parenthese (int i, char s){
            this.indx = i;
            this.symb = s;
        }
    }
}

动态规划法 Dynamic Programming 复杂度

时间 O(N) 空间 O(N)

思路

动态规划法将大问题化为小问题，我们不一定要一下子计算出整个字符串中最长括号对，我们可以先从后向前，一点一点计算。假设d[i]是从下标i开始到字符串结尾最长括号对长度，s[i]是字符串下标为i的括号。如果s[i-1]是左括号，如果i + d[i] + 1是右括号的话，那d[i-1] = d[i] + 1。如果不是则为0。如果s[i-1]是右括号，因为不可能有右括号开头的括号对，所以d[i-1] = 0。

代码

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

后续 Follow Up

Q：能否不用额外空间求解？
A：可以，但是要提高时间复杂度。比如((()())，先遍历一遍将所有的()替换成00，得到((0000)，再遍历一遍，替换所有的(00...00)这种形式字符串为000...000，这里我们得到(000000，直到遍历完无法替换更多括号为之。如果所有符号都是0，说明是有效的。这样的时间复杂度是O(N)。

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/66168.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

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论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
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0