每日一题：Leetcode-32 最长有效括号

力扣题目

解题思路

java代码

力扣题目：

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

子串

的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

解题思路：

• 首先在 longestValidParentheses 方法中，定义了变量 maxans 来存储最长有效括号子串的长度，创建了一个整数数组 dp ，其长度与输入字符串 s 相同。

• 然后通过一个循环从第二个字符开始遍历字符串。

• 当遇到 ) 时，分两种情况进行处理：

  • 如果前一个字符是 ( ，则 dp[i] 的值为 (i >= 2? dp[i - 2] : 0) + 2 。这意味着如果当前位置 i 之前至少有两个字符，那么当前有效括号子串的长度为前两个位置的 dp 值（如果有）加上 2；否则，直接为 2。
  • 如果前一个字符也是 ) ，并且在当前位置减去前一个有效括号子串长度再往前一个位置的字符是 ( ，则 dp[i] 的值为 dp[i - 1] + ((i - dp[i - 1]) >= 2? dp[i - dp[i - 1] - 2] : 0) + 2 。这表示当前有效括号子串的长度为前一个有效括号子串的长度，加上当前位置与前一个有效括号子串之间可能存在的有效括号子串长度（如果有），再加上 2 。

• 在每次循环中，都更新 maxans 为当前 dp[i] 和之前的 maxans 中的最大值。

例如，对于输入字符串 ")()())" ：

• 从第二个字符开始，遇到 ) 且前一个是 ( ，dp[1] = 2 。
• 继续，遇到第三个 ) ，由于不满足前面的条件，dp[2] = 0 。
• 遇到第四个 ) ，满足第二种情况，dp[3] = dp[1] + 2 = 4 。

最终返回的 maxans 就是最长有效括号子串的长度。

java代码：

package org.example.mouth7.today23;

public class Leetcode32 {
    public static void main(String[] args) {
        String s = ")()())";
        System.out.println(longestValidParentheses(s));
    }
    public static 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 - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

更多详细内容同步到公众号，感谢大家的支持！

每天都会给刷算法的小伙伴推送明日一题，并且没有任何收费项