Longest Valid Parentheses

Problem

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.

Related Topics:

String Dynamic Programming

Analysis

方法一：动态规划，建立数组，遍历的同时，记录有效长度。只有当遇到 ) 时，才可能存在有效字符串，所以仅在遇到 ) 时进行判断。

• 当遇到 () 的情况时，其自身长度为 2，同时需要加上之前存在的有效长度 dp[i-2]。
• 当遇到 )) 的情况时，首先需要确定后一个 ) 是否有对应的 ( 存在。若存在，其自身 2，加上 ( 之前的有效长度 dp[i - 2 - dp[i - 1]]，以及其内部所包含的长度 dp[i - 1]。

方法二：方法一是有效长度的累加，而方法二则是字符串两端相减，来得到长度。利用栈来实现，遇到 ( 时，将下标压入栈内，当遇到 ) 时，弹出栈顶元素，其与下个元素的差值，便是有效长度。

方法三：扫描，设置两个变量 left，right 来统计遇到的 ( 和 ) 的数量。

• 当 left == right 时，为有效字符串，其长度为 left * 2。
• 当 left < right 时，必不可能形成有效字符串，重置 left，right。
• 由于无法判断 left > right 的情况，所以需要再来一次逆向扫描。

Code

累加：

class Solution {

    fun longestValidParentheses(s: String): Int {

        val dp = IntArray(s.length)
        var max = 0

        for (i in 1 until s.length) {
            dp[i] = when {
                s[i] == ')' && s[i - 1] == '(' ->
                    (if (i >= 2) dp[i - 2] else 0) + 2
                s[i] == ')' && i - 1 >= dp[i - 1] && s[i - 1 - dp[i - 1]] == '(' ->
                    dp[i - 1] + (if (i - 2 >= dp[i - 1]) dp[i - 2 - dp[i - 1]] else 0) + 2
                else -> 0
            }
            max = maxOf(max, dp[i])
        }

        return max
    }
}

相减：

class Solution {

    fun longestValidParentheses(s: String): Int {

        val stack = java.util.Stack<Int>()
        stack.push(-1)

        var max = 0
        for (i in s.indices) {

            when {
                s[i] == '(' -> stack.push(i)
                else -> {
                    stack.pop()
                    when {
                        stack.empty() -> stack.push(i)
                        else -> max = maxOf(max, i - stack.peek())
                    }
                }
            }
        }

        return max
    }
}

扫描：

class Solution {

    fun longestValidParentheses(s: String): Int {

        return maxOf(s.scan(true), s.scan(false))
    }

    private fun String.scan(leftToRight: Boolean): Int {

        var left = 0
        var right = 0
        var max = 0
        var index = if (leftToRight) 0 else this.lastIndex
        val step = if (leftToRight) 1 else -1

        while (index < this.length && index > -1) {

            when (this[index]) {
                '(' -> left++
                ')' -> right++
            }

            when {
                left == right -> max = maxOf(max, left)
                (leftToRight && left < right) || (!leftToRight && left > right) -> {
                    left = 0
                    right = 0
                }
            }

            index += step
        }

        return max * 2
    }
}