首页 > 其他 > 详细

32. 最长有效括号 - LeetCode

时间:2021-02-15 23:42:47      阅读:26      评论:0      收藏:0      [点我收藏+]

32. 最长有效括号

题目链接

两遍扫描

  • 先从左往右扫描,记录未匹配的左括号数目

    • 若等于0,则记录当前子串长度
    • 若小于0,则匹配失败,将下一个位置作为子串起点
    • 若大于0,则继续匹配
  • 从右往左再进行一次相同的扫描,就可以考虑到左括号比右括号多的情况

    • 因为从左往右扫描,左括号比右括号多的时候,会继续往右寻找右括号,而不是减少左括号
class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        if(len == 0) return 0;
        int ans = 0;
        int i = 0, j = 0, num = 0;
        for(; j < len; j++){
            if(s.charAt(j) == ‘(‘)
                num++;
            else{
                if(num == 0)
                    i = j + 1;
                else {
                    num--;
                    if(num == 0)
                        ans = Math.max(ans, j-i+1);
                }
            }
        }
        i = len - 1; j = len - 1; num = 0;
        for(;i >= 0; i--){
            if(s.charAt(i) == ‘)‘)
                num++;
            else{
                if(num == 0)
                    j = i - 1;
                else {
                    num--;
                    if(num == 0)
                        ans = Math.max(ans, j-i+1);
                }
            }
        }
        return ans;
    }
}
  • 时间复杂度为O(n),空间复杂度为O(1)

动态规划

  • dp[i]表示以第i个字符结尾的最长有效括号长度,分情况讨论:
    • s[i] == ‘(‘,dp[i] = 0
    • s[i] == ‘)‘:
      • 若s[i-1] == ‘(‘,则构成"...()",dp[i] = dp[i-2] + 2;
      • 若s[i-1] == ‘)‘,若要有效,必须构成"...((...))",即s[i-dp[i-1]-1] == ‘(‘,此时dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        if(len == 0) return 0;
        int[] dp = new int[len];
        int ans = 0;
        dp[0] = 0;
        for(int i = 1; i < len; i++){
            if(s.charAt(i) == ‘(‘)
                dp[i] = 0;
            else if(s.charAt(i-1) == ‘(‘)
                dp[i] = 2 + (i >= 2 ? dp[i-2] : 0);
            else if(i - dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == ‘(‘)
                dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i-dp[i-1]-2] : 0);
            else dp[i] = 0;
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
  • 时间复杂度为O(n),空间复杂度为O(n)

32. 最长有效括号 - LeetCode

原文:https://www.cnblogs.com/xiafrog/p/14403967.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!