daily leetcode - longest-valid-parentheses - !

题目地址

https://leetcode.com/problems/longest-valid-parentheses/

题目描述

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

思路

这道求最长有效括号比之前那道 Valid Parentheses 难度要大一些,这里还是借助栈来求解,需要定义个 start 变量来记录合法括号串的起始位置,遍历字符串,如果遇到左括号,则将当前下标压入栈,如果遇到右括号,如果当前栈为空,则将下一个坐标位置记录到 start,如果栈不为空,则将栈顶元素取出,此时若栈为空,则更新结果和 i - start + 1 中的较大值,否则更新结果和 i - st.top() 中的较大值,参见代码如下:

解法一:

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0, start = 0, n = s.size();
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') st.push(i);
            else if (s[i] == ')') {
                if (st.empty()) start = i + 1;
                else {
                    st.pop();
                    res = st.empty() ? max(res, i - start + 1) : max(res, i - st.top());
                }
            }
        }
        return res;
    }
};

还有一种利用动态规划 Dynamic Programming 的解法,可参见网友喜刷刷的博客。这里使用一个一维 dp 数组,其中 dp[i] 表示以 s[i-1] 结尾的最长有效括号长度(注意这里没有对应 s[i],是为了避免取 dp[i-1] 时越界从而让 dp 数组的长度加了1),s[i-1] 此时必须是有效括号的一部分,那么只要 dp[i] 为正数的话,说明 s[i-1] 一定是右括号,因为有效括号必须是闭合的。当括号有重合时,比如 "(())",会出现多个右括号相连,此时更新最外边的右括号的 dp[i] 时是需要前一个右括号的值 dp[i-1],因为假如 dp[i-1] 为正数,说明此位置往前 dp[i-1] 个字符组成的子串都是合法的子串,需要再看前面一个位置,假如是左括号,说明在 dp[i-1] 的基础上又增加了一个合法的括号,所以长度加上2。但此时还可能出现的情况是,前面的左括号前面还有合法括号,比如 "()(())",此时更新最后面的右括号的时候,知道第二个右括号的 dp 值是2,那么最后一个右括号的 dp 值不仅是第二个括号的 dp 值再加2,还可以连到第一个右括号的 dp 值,整个最长的有效括号长度是6。所以在更新当前右括号的 dp 值时,首先要计算出第一个右括号的位置,通过 i-3-dp[i-1] 来获得,由于这里定义的 dp[i] 对应的是字符 s[i-1],所以需要再加1,变成 j = i-2-dp[i-1],这样若当前字符 s[i-1] 是左括号,或者j小于0(说明没有对应的左括号),或者 s[j] 是右括号,此时将 dp[i] 重置为0,否则就用 dp[i-1] + 2 + dp[j] 来更新 dp[i]。这里由于进行了 padding,可能对应关系会比较晕,大家可以自行带个例子一步一步执行,应该是不难理解的,参见代码如下:

解法二:

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0, n = s.size();
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; ++i) {
            int j = i - 2 - dp[i - 1];
            if (s[i - 1] == '(' || j < 0 || s[j] == ')') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i - 1] + 2 + dp[j];
                res = max(res, dp[i]);
            }
        }
        return res;
    }
};

此题还有一种不用额外空间的解法,使用了两个变量 left 和 right,分别用来记录到当前位置时左括号和右括号的出现次数,当遇到左括号时,left 自增1,右括号时 right 自增1。对于最长有效的括号的子串,一定是左括号等于右括号的情况,此时就可以更新结果 res 了,一旦右括号数量超过左括号数量了,说明当前位置不能组成合法括号子串,left 和 right 重置为0。但是对于这种情况 "(()" 时,在遍历结束时左右子括号数都不相等,此时没法更新结果 res,但其实正确答案是2,怎么处理这种情况呢?答案是再反向遍历一遍,采取类似的机制,稍有不同的是此时若 left 大于 right 了,则重置0,这样就可以 cover 所有的情况了,参见代码如下:

解法三:

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0, left = 0, right = 0, n = s.size();
        for (int i = 0; i < n; ++i) {
            (s[i] == '(') ? ++left : ++right;
            if (left == right) res = max(res, 2 * right);
            else if (right > left) left = right = 0;
        }
        left = right = 0;
        for (int i = n - 1; i >= 0; --i) {
            (s[i] == '(') ? ++left : ++right;
            if (left == right) res = max(res, 2 * left);
            else if (left > right) left = right = 0;
        }
        return res;
    }
};

思路2(动态规划)

所有的动态规划问题, 首先需要解决的就是如何寻找合适的子问题.
该题需要我们找到最长的有效括号对, 我们首先想到的就是定义dp[i]为前i个字符串的最长有效括号对长度, 但是随后我们会发现, 这样的定义, 我们无法找到dp[i]和dp[i-1]的任何关系.
所以, 我们需要重新找一个新的定义: 定义dp[i]为以第i个字符结尾的最长有效括号对长度. 然后, 我们通过下面这个例子找一下dp[i]和dp[i-1]之间的关系.

s = '(())())'

从上面的例子我们可以观察出一下几点结论(描述中i为图中的dp数组的下标, 对应s的下标应为i-1, 第i个字符的i从1开始).

  1. base case: 空字符串的最长有效括号对长度肯定为0, 即: dp[0] = 0;
  2. s的第1个字符结尾的最长有效括号对长度为0, s的第2个字符结尾的最长有效括号对长度也为0, 这个时候我们可以得出结论: 最长有效括号对不可能以 (结尾, 即: dp[1] = d[2] = 0;
  3. 当i等于3时, 我们可以看出dp[2]=0, dp[3]=2, 因为第2个字符(s[1])和第3个字符(s[2])是配对的;
    当i等于4时, 我们可以看出dp[3]=2, dp[4]=4, 因为我们配对的是第1个字符(s[0])和第4个字符(s[3]);
    因此, 我们可以得出结论: 如果第i个字符和第i-1-dp[i-1]个字符是配对的, 则dp[i] = dp[i-1] + 2, 其中: i-1-dp[i-1] >= 1, 因为第0个字符没有任何意义;
  4. 根据第3条规则来计算的话, 我们发现dp[5]=0, dp[6]=2, 但是显然, dp[6]应该为6才对, 但是我们发现可以将"(())"和"()"进行拼接, 即: dp[i] += dp[i-dp[i]], 即: dp[6] = 2 + dp[6-2] = 2 + dp[4] = 6

根据以上规则, 我们求解dp数组的结果为: [0, 0, 0, 2, 4, 0, 6, 0], 其中最长有效括号对的长度为6. 以下为图解:
mark

关键点解析

  1. 第3点特征, 需要检查的字符是s[i-1]和s[i-2-dp[i-1]], 根据定义可知: i-1 >= dp[i-1], 但是i-2不一定大于dp[i-1], 因此, 需要检查越界;
  2. 第4点特征最容易遗漏, 还有就是不需要检查越界, 因为根据定义可知: i >= dp[i], 所以dp[i-dp[i]]的边界情况是dp[0];

代码

  • 语言支持: Python

Python Code:

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        mlen = 0
        slen = len(s)
        dp = [0] * (slen + 1)
        for i in range(1, len(s) + 1):
            # 有效的括号对不可能会以'('结尾的
            if s[i - 1] == '(':
                continue

            left_paren = i - 2 - dp[i - 1]
            if left_paren >= 0 and s[left_paren] == '(':
                dp[i] = dp[i - 1] + 2

                # 拼接有效括号对
                if dp[i - dp[i]]:
                    dp[i] += dp[i - dp[i]]

                # 更新最大有效扩对长度
                if dp[i] > mlen:
                    mlen = dp[i]

        return mlen

扩展

  1. 如果判断的不仅仅只有'('和')', 还有'[', ']', '{'和'}', 该怎么办?
  2. 如果输出的不是长度, 而是任意一个最长有效括号对的字符串, 该怎么办?
    本文参考自:
    https://github.com/grandyang/leetcode/ &
    https://github.com/azl397985856/leetcode

标题: daily leetcode - longest-valid-parentheses - !
文章作者: lonuslan
文章链接: https://www.lonuslan.com/articles/2020/02/03/1580711187283.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LonusLan
    评论
    0 评论
avatar

取消