Jamzen的技术博客
0%

LeetCode.最长有效括号

发表于 分类于 Valine：

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

  • 示例 1:
    输入: “(()”
    输出: 2
  • 示例 2:
    输入: “)()())”
    输出: 4

解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
object LongestValidParentheses {
  def main(args: Array[String]): Unit = {
    println(longestValidParentheses("(()"))
    println(longestValidParentheses(")()())"))
  }

  /**
   * 暴力解法， 前后两个指针判断是否为有效括号
   */
  def longestValidParentheses(str: String): Int = {
    if (str.length < 2) return 0
    var res = 0

    val stack = new java.util.Stack[Char]()
    for (i <- 0 until str.length - 1) {
      if (str.charAt(i) == '(') {
        stack.clear()
        stack.push(str.charAt(i))
        breakable(for (j <- i + 1 until str.length) {
          if (str.charAt(j) == '(') {
            stack.push('(')
          } else {
            if (!stack.isEmpty) {
              stack.pop()
              if (stack.isEmpty()) {
                res = Math.max(res, j - i + 1)
              }
            } else {
              break()
            }
          }
        })
      }
    }
    res
  }

  def longestValidParentheses2(str: String): Int = {
    if (str.length < 2) return 0
    var res = 0


    res
  }
}