hard►leetcode

LeetCode 32. Longest Valid Parentheses

Problem

LeetCode 32. Longest Valid Parentheses

1. 题目简述

给出一个仅有”(“和”)”组成的字符串，找出其中最长的valid的括号匹配字符串长度。例如：

Example 1:

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

Example 2:

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

2. 算法思路

相关问题：

  1. LeetCode 20. Valid Parentheses(无解析)

一开始的想法也是动态规划，但是dp的思路出了点问题，直接看下面这个思路即可。

dynamic programming

  1. 假设dp[i]表示以第i-1个元素为结尾，最长的valid的长度；这里我们要注意，这里的dp值是以当前为结尾，而不是在此之前的最长长度！！！
  2. 那么当s[i]为”(“时，那么dp[i] = 0;
  3. 当s[i]为”)”时，分为两种情况。第一种：如果s[i - 1]为’(‘，dp[i] = dp[i - 1] + 2;
  4. 第二种情况：如果s[i - 1]为’)’，那么逻辑复杂一点，倘若dp[i - dp[i - 1] - 1] == ‘(‘，那么dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]；倘若dp[i - dp[i - 1] - 1] == ‘)’，那么说明其无法凑成对，仍然是0。
class Solution {
    public int longestValidParentheses(String s) {
        if (s.length() <= 1) {
            return 0;
        }

        int n = s.length();
        int[] dp = new int[n];
        char[] arr = s.toCharArray();
        int longest = 0;

        // 初始化dp
        if (arr[0] == '(' && arr[1] == ')') {
            dp[1] = 2;
        }
        longest = dp[1];

        // 从index为2开始遍历，只有当前字符为')'且和前面某个'('匹配时，才会更新dp值，否则都为0！
        for (int i = 2; i < n; i++) {
            if (arr[i] == ')' && arr[i - 1] == '(') {
                dp[i] = dp[i - 2] + 2;
            } else if (arr[i] == ')' && arr[i - 1] == ')') {
                if (i - dp[i - 1] - 1 >= 0 && arr[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] - 2) >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                }
            }
            longest = Math.max(dp[i], longest);
        }

        return longest;
    }
}

Stack

使用stack的方式十分巧妙，通过记录上一次不合法括号的最后的index来判断。每次遇到一个合法的’)’时，计算一下以当前的’)’结尾的子串的最长合法长度是多少。代码如下（直接抄的solution）：

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;
    }
}