LeetCode.32.最长有效括号（困难）

题目

LeetCode.32.最长有效括号（困难）

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

题解

解法1：双指针

括号匹配时，左右括号数量相等，子串长度就是左右括号之和。

可以从左到右遍历字符串，记录左右括号的数量，通过数量来判断子串是否是是有效括号。

• 当右括号数量大于左括号时，当前子串肯定不是有效的括号，计数对于累加有效括号子串已经无意义，可以清零，以便后续子串。
• 当左括号数量大于右括号，有可能还有匹配的右括号在后面，只要右括号数量跟左括号相等，就可以认定当前子串是有效的括记录子串长度，并比较最长的长度。
  • 这种情况下有可能最终左括号的数量一直大于右括号数量，导致无法触发记录，例如((((((((((())。
  • 此时可以从右向左再遍历一次字符串，就可以触发到左右括号相等的时候，当左括号数量大于右括号，括号数量计数清零。

class Solution {
    fun longestValidParentheses(s: String): Int {
        var maxLength = 0
        var left = 0
        var right = 0
        for (i in s.indices) {
            when (s[i]) {
                '(' -> left++
                ')' -> right++
            }
            when {
                left == right -> maxLength = maxOf(maxLength, 2 * right)
                right > left -> {
                    left = 0
                    right = 0
                }
            }
        }
        left = 0
        right = 0
        for (i in s.length - 1 downTo 0) {
            when (s[i]) {
                '(' -> left++
                ')' -> right++
            }
            when {
                left == right -> maxLength = maxOf(maxLength, 2 * left)
                right < left -> {
                    left = 0
                    right = 0
                }
            }
        }
        return maxLength
    }
}

解法2：栈

怎么计算有效括号长度？

从左到右遍历字符串时，发现如果有一个子串是有效括号，要计算它的长度，就是用结束索引减去起始索引得到长度。所以的想办法记录左括号的起始索引。

怎么存储索引比较合适？

从左到右遍历发现右括号后，得知道左边有没有左括号，如果有，计算括号匹配长度是要知道这个左括号前面一个位置的索引。

如果发现了多个右括号，是要从右到左依次访问匹配的左括号前面一个位置的索引，遍历顺序和访问顺序相反，可以用栈来存储左括号索引。

遍历到右括号时，发现栈不为空说明有左括号，匹配到左括号出栈后，栈顶就是匹配的左括号的前一个位置的索引。

如果匹配的左括号出栈后栈为空，就要手动记录一下第一个左括号左边的索引。

何时入栈？

有效括号子串的第一个字符一定是一个左括号，因为如果开头是右括号则不是有效括号子串。
所以遇到左括号就要记录其索引，因为它有可能是一个长的有效括号子串的起始索引。

import kotlin.math.max

class Solution {
    fun longestValidParentheses(s: String): Int {
        var maxLength = 0
        val left = Stack<Int>()
        // 记录可能的有效括号子串的前一个位置，可以利用此索引计算子串的长度
        var prev = -1
        for (i in s.indices) {
            when (s[i]) {
                '(' -> left.push(i)
                ')' -> {
                    // 遇到右括号，如果前面有左括号，说明匹配
                    if (left.isNotEmpty()) {
                        // 匹配的左括号从栈中移出
                        left.pop()
                        // 如果前面还有左括号，这个左括号的索引是刚才有效括号子串的前一个位置
                        // 如果前面没有左括号了，读取遇到左括号前记录的位置，也是刚才有效括号子串的前一个位置
                        val prevOfStart = if (left.isNotEmpty()) left.peek() else prev
                        // 当前位置减去有效括号子串的前一个位置就是有效括号子串的长度
                        val length = i - prevOfStart
                        // 记录最大长度
                        maxLength = max(maxLength, length)
                    } else {
                        // 遇到右括号，但前面没有左括号，说明当前字符结尾的子串没办法构成有效括号
                        // 但后面的子串还有可能是有效的子串，记录当前位置，如果后面紧接着的子串是有效括号子串，可以利用此索引计算子串的长度
                        prev = i
                    }
                }
            }
        }
        return maxLength
    }
}

解法3：动态规划

最值问题考虑用动态规划。尝试划分为子问题+有限步骤。

如果字符串s是一个有效的括号串，最后一个字符一定是右括号。

• 如果最后一个字符不是右括号，去除最后一个字符查看前面的子串是不是有效括号，前面子串查看方法是一样的。
• 如果最后一个字符是右括号：
  • 倒数第二个字符是左括号，发生了一次匹配，有效括号长度可以加2了，再继续看前面的子串的有效括号的长度。
  • 倒数第二个字符是右括号，得看前面的有没有左括号能跟最后一个右括号匹配上才行。

递归

class Solution {
    fun longestValidParentheses(s: String): Int {
        val n = s.length
        var maxLength = 0
        fun longest(i: Int): Int {
            if (i <= 0) return 0
            var length = 0
            if (s[i] == ')') {
                when (s[i - 1]) {
                    '(' -> length = 2 + longest(i - 2)
                    ')' -> {
                        val midLen = longest(i - 1)
                        val left = i - 1 - midLen
                        // 看前面有没有跟s[i]这个右括号匹配的左括号
                        if (left >= 0 && s[left] == '(') {
                            // 匹配到左括号前面的有效括号子串长度还要加上
                            length = 2 + midLen + longest(left - 1)
                        }
                    }
                }
            }
            if (length > maxLength) maxLength = length
            longest(i - 1)
            return length
        }
        longest(n - 1)
        return maxLength
    }
}

记忆化递归

暴力递归有很多重叠子问题。

例如两次longest(i - 1)和一次longest(i - 2)计算结果是一样的，但是都重复计算了。

需要记录中间计算状态。

class Solution {
    fun longestValidParentheses(s: String): Int {
        val n = s.length
        var maxLength = 0
        val memo = IntArray(n) { -1 }
        fun longest(i: Int): Int {
            if (i <= 0) return 0
            if (memo[i] != -1) return memo[i]
            var length = 0
            if (s[i] == ')') {
                when (s[i - 1]) {
                    '(' -> length = 2 + longest(i - 2)
                    ')' -> {
                        val midLen = longest(i - 1)
                        val left = i - 1 - midLen
                        // 看前面有没有跟s[i]这个右括号匹配的左括号
                        if (left >= 0 && s[left] == '(') {
                            // 匹配到左括号前面的有效括号子串长度还要加上
                            length = 2 + midLen + longest(left - 1)
                        }
                    }
                }
            }
            memo[i] = length
            if (length > maxLength) maxLength = length
            longest(i - 1)
            return length
        }
        longest(n - 1)
        return maxLength
    }
}

自底向上动态规划

设dp[i]表示以字符s[i]结尾的最长有效的括号子串的长度。

状态转移方程按照递归的方式写就行了。

边界条件单独判断一下就OK。

class Solution {
    fun longestValidParentheses(s: String): Int {
        val n = s.length
        var maxLength = 0
        val dp = IntArray(n) { 0 }
        // 从第2个字符开始遍历，一个字符无法形成有效括号
        for (i in 1 until n) {
            if (s[i] == ')') {
                when (s[i - 1]) {
                    '(' -> dp[i] = 2 + if (i < 2) 0 else dp[i - 2]
                    ')' -> {
                        val midLen = dp[i - 1]
                        val left = i - 1 - midLen
                        if (left >= 0 && s[left] == '(') {
                            dp[i] = 2 + midLen + if (left == 0) 0 else dp[left - 1]
                        }
                    }
                }
            }
            maxLength = maxOf(maxLength, dp[i])
        }
        return maxLength
    }
}