32、最长有效括号

leetcode 动态规划、栈
Created At :
Count:1.7k Views 👀 : Comment:
  1. 33、最长合法子括号串
    1. Example 1:
    2. Example 2:
  2. 题解
    1. 1、 暴力法 $Time:O(n^2) Space:O(n)$
    2. 2、 动态规划法
    3. 3、 巧用栈解，栈存储有效的字串的下标。
      1. java实现
      2. kotlin实现
    4. 4、 统计左右括号的数量，来回两遍遍历

33、最长合法子括号串

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

链接：https://leetcode-cn.com/problems/longest-valid-parentheses

题解

1、 暴力法 $Time:O(n^2) Space:O(n)$

  • 枚举每一个子串，字串间的长度是2的整数倍
  • 判断是否是合法的字串
    • 利用栈判断，遍历字串，如果是 ( ,入栈。否则：如果栈非空且栈顶元素是 ( ,则弹出栈顶元素。若 栈提前变空，以及栈顶元素不为 (, 则不是合法串。最后，根据栈是否为空，判断是否是合法字串。——栈的应用，括号匹配。
    • 是合法的，计算其长度，更新最长字串
public class Solution {
    // 基于栈的有效括号的判断
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push('(');
            } else if (!stack.empty() && stack.peek() == '(') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.empty();
    }
    public int longestValidParentheses(String s) {
        int maxlen = 0;
        // 枚举每个位置
        for (int i = 0; i < s.length(); i++) {
            // 二级枚举两个位置
            for (int j = i + 2; j <= s.length(); j+=2) {
                // 判断子串否满足要求
                if (isValid(s.substring(i, j))) {
                    // 更新最长子串
                    maxlen = Math.max(maxlen, j - i);
                }
            }
        }
        return maxlen;
    }
}

2、 动态规划法

  • 遍历一遍字符串，一个辅助数组dp[],dp[i]表示以s[i]结尾的最长合法字串的长度。初始状态下dp[i] = 0，由于当s[i] = '('时，dp[i] === 0,我们只需要更新当s[i] = ')'时的dp[i]即可。
  • dp[i]的递推分析：
    • 当s[i] = '(',s[i - 1] = ')'时，dp[i] = dp[i - 2] + 2，因为dp[i-1] === 0，而dp[i - 2] >= 0。此时，最优的局部解长度增加2。这一步，需要注意，()为s的前缀时的处理：i >= 2 ? dp[i - 2] : 0。
    • 当s[i] = ')', s[i - 1] = ')'时，如果当前的最长字串长度小于i，且s[i - dp[i - 1] -1] = '('，这样s[i]就存在对应的匹配，从而：dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 或者 dp[i] = dp[i - 1] + 2。其实，若 dp[i] > 0，可以得出，s[i - dp[i - 1] + 1] = '(',s[i] = ')'。这种情况的字串如："sub0(sub1)"，sub0和(sub1)都是合法字串，属于并列合法字串，没有嵌套。
public class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int dp[] = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            // 遇到左括号
            if (s.charAt(i) == ')') {
                // 前序有右括号
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 更新dp[i]的括号长度
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}
  • kotlin实现
import kotlin.math.max
class Solution {
    private var maxLength = 0

    /**
     * 递归和动态规划关键在于把原问题拆分为子问题和一系列当前步骤
     * 按照划分子问题的经验一般是从后向前推导，在这个方向上找规律
     * 一个有效的括号子串，最后一个字符一定是右括号，因为如果最后一个字符是左括号它就不是有效的括号子串
     */
    fun longestValidParentheses(s: String): Int {
        maxLength = 0
        val memo = IntArray(s.length) { -1 }
        dp(s, s.length - 1, memo)
        return maxLength
    }

    /** dp[i]表示以字符s[i]结尾的最长有效的括号子串的长度 */
    private fun dp(s: String, i: Int, memo: IntArray): Int {
        if (i <= 0) return 0

        if (memo[i] >= 0) return memo[i]

        var length = 0
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                length = 2 + dp(s, i - 2, memo)
            } else if (s[i - 1] == ')') {
                // s[i-1]是右括号，判断前面有没有匹配的左括号
                val prevLength = dp(s, i - 1, memo)
                if (i - 1 - prevLength >= 0 && s[i - 1 - prevLength] == '(') {
                    // 有的话整个子串的长度还要加上左括号前面的有效括号子串长度
                    length = 2 + dp(s, i - 1, memo) + dp(s, i - 1 - prevLength - 1, memo)
                }
            }
        }

        memo[i] = length
        maxLength = max(maxLength, length)

        dp(s, i - 1, memo)

        return length
    }

}

3、 巧用栈解，栈存储有效的字串的下标。

  • 遍历一遍字符串
    • 当前s[i] = '('，则将 i 入栈，否则：栈顶元素出栈，此时，如果栈为空，将i 入栈，s[i]肯定为')'；不为空，更新当前最长合法字串的长度。
    • 栈中需要多一个辅助的元素，便于计算合法字符串的长度。初始为-1，而后，根据情况入栈。

java实现

public class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);// 标记点
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);// 标记点
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}

kotlin实现

class Solution {
    fun longestValidParentheses(s: String): Int {
        val stack = LinkedList<Int>()
        var ans = 0

        val search: ((Int) -> Unit) = {
            if (stack.isNotEmpty()) {
                stack.pop()
                if (stack.isNotEmpty() && stack.peek() > 0) {
                    stack.push(it + stack.pop() + 1)
                } else {
                    stack.push(it + 1)
                }
                ans = Math.max(ans,stack.peek())
            }
        }
        for (char in s) {
            if (char == '(') {
                stack.push(-1)
            } else {
                if (stack.peek() == -1) {
                    search(0)
                } else {
                    if (stack.isNotEmpty()  && stack.peek() > 0) {
                        search(stack.pop())
                    }
                }
            }
        }
        return ans * 2;
    }
}

4、 统计左右括号的数量，来回两遍遍历

  • left 记录左括号的数量， right记录右括号的数量
  • 第一遍，从左至右遍历
    • 遇到左括号么，left++ 右括号 right++
    • left == right，到最后了，更新最长合法字串
    • left <= right, left = right = 0 非法了，重新开始
  • 第二遍，从右至左遍历
    • 遇到左括号么，left++ 右括号 right++
    • left == right，更新最长合法字串
    • left >= right, left = right = 0 非法了，重新开始
public class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        // 从前往后
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right >= left) {// 非法了，重新开始
                left = right = 0;
            }
        }
        // 从后往前
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left >= right) {// 非法了，重新开始
                left = right = 0;
            }
        }
        return maxlength;
    }
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com

💰

Title:32、最长有效括号

Count:1.7k

Author:攀登

Created At:2020-07-26, 00:19:44

Updated At:2024-06-15, 15:52:32

Url:http://jiafeimao-gjf.github.io/2020/07/26/32%E3%80%81%E6%9C%80%E9%95%BF%E6%9C%89%E6%95%88%E6%8B%AC%E5%8F%B7/

Copyright: 'Attribution-non-commercial-shared in the same way 4.0' Reprint please keep the original link and author.

©2019-？ Pandeng

Built with Hexo and 3-hexo theme

×

Help us with donation