LeetcCode 32. Longest Valid Parentheses

[Woodyiiiiiii]

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 "()()"

---

这道题要求我们找到字符串内有效括号的最大长度。我自己写的代码对“(())((((()(())”这种“有效区间”情况无法判断，也就说我只能判断前面的“(())”部分，后面“()(())”无法判断。

说到底其实我对括号匹配没有深度理解。我们需要的是遍历到“)”时找到在它之前离它最近的“(”，所以需要用栈存储左括号的位置；取出左括号位置后，即保证这两个括号有效了，我们需要计算两个括号之间的距离，所以需要一开始保存一个变量start记录可能出现有效括号匹配的区间起点，如果栈空则计算“)”到start的距离，否则直接计算“)”到栈顶元素(前一个“(”)的距离。Brute Force代码如下：

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int res = 0, start = 0;
        Stack<Integer> left = new Stack<>();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '(') left.push(i);
            else if (s.charAt(i) == ')') {
                if (left.empty()) {
                    start = i + 1;
                }else {
                    left.pop();
                    res = (left.empty()) ? Math.max(res, i - start + 1) :
                        Math.max(res, i - left.peek());
                }
            }
        }
        return res;
    }
}

以上stack的写法关键是使用一个变量(start)去存储新的区间起点。举例“")()())"”和“(())((((()(())”。

进一步，我们可以发现每个子问题的解都是靠前一个子问题求得的，具有无效性，所以可以使用DP解法。创建一个DP数组，长度为n + 1，dp[i]表示字符串中以i - 1结尾的子字符串有效匹配括号长度(之所以是i - 1是因为如果是i则i - 1会溢出)，而且保证当前字符包括在内，所以不是直接返回dp[n]，而是遍历时都会判断，总共n次判断。我们不需要用栈来存储左括号位置，因为DP数组中有上一个位置的元素已经存储相关信息。

计算start的公式是i - 2 - dp[i - 1]，即保证有效的情况下减去上一个有效长度再减去自身的两个括号长度。首先如果当前字符是左括号或者开始位置小于0或开始位置之后的字符是”)“则为无效；有效情况下，当前dp[i] = dp[i - 1] + 2 + dp[j]，dp[j]保证我我开头说的那种多个有效长度在一起的情况可以被计算。

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int res = 0;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            int j = i - 2 - dp[i - 1];
            if (s.charAt(i - 1) == '(' || j < 0 || s.charAt(j) == ')') {
                dp[i] = 0;
            }else {
                dp[i] = dp[i - 1] + 2 + dp[j];
                res = Math.max(res, dp[i]);
            }
        } q
        return res;
    }
}

---

参考资料：

• https://leetcode.com/problems/longest-valid-parentheses/
• [LeetCode] 32. Longest Valid Parentheses grandyang/leetcode#32