【牛客】最长的括号子串
浏览 119 | 评论 0 | 字数 1104
TTQ
2022年04月23日
  • 原题链接:https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad

    描述

    给出一个长度为 n 的,仅包含字符 '(' 和 ')' 的字符串,计算最长的格式正确的括号子串的长度。

    例1: 对于字符串 "(()" 来说,最长的格式正确的子串是 "()" ,长度为 2 .
    例2:对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ,长度为 4 .

    思路

    可以想到,从左向右扫描时,当")"数量比"("多时,括号字串已不合法,故此时将计数器清空,当两种括号数量相同时,更新最大值,但这样会漏掉一种情况:左括号的数量始终大于右括号的数量,如((),这种情况求不出最长有效括号,所以还需要从右往左再扫描一次,当然判定条件要反过来。

    代码

    /**
     *
     * @param s string字符串
     * @return int整型
     */
    function longestValidParentheses(s) {
      let left = 0;
      let right = 0;
      let max = 0;
    
      for (let i = 0; i < s.length; i++) {
        if (s[i] == "(") left++;
        if (s[i] == ")") right++;
    
        if (right > left) {
          right = left = 0;
          continue;
        }
        if (left === right) {
          max = Math.max(max, left);
        }
      }
      left = right = 0;
      for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] == "(") left++;
        if (s[i] == ")") right++;
    
        if (right < left) {
          right = left = 0;
          continue;
        }
        if (left === right) {
          max = Math.max(max, right);
        }
      }
      return max * 2;
    }
    本文作者:TTQ
    本文链接:https://blog.ponder.fun/archives/148.html
    最后修改时间:2022-04-23 21:24:36
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论