32. 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: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
最左如果是')',最右如果是‘(’。可以直接排除

Example 3:
Input: s = ""
Output: 0
为空的时候直接返回零

Constraints:
0 <= s.length <= 3 * 104 #不能用暴力法，必然超时
s[i] is '(', or ')'.

思考

简单的就是可以通过栈的入栈和出栈，来判断成对的括号。
从第一次接收到左括号开始入栈，然后遇到一次栈为空的情况就计数长度。
如果遇到了一次错误的序列，如多余的右括号，将栈清空，从栈的下一位开始重新计数。直到结尾。
比较并记录最大的长度。
再加上这边对重新计算长度的部分，可以作为独立的一部分，所以可以使用递归表示。

难点:
从头开始遍历的话，无法判定何时进入下一次迭代。会存在 '()(()' ')(()((' 等一系列的类似情况。会存在没有栈始终没有空的情况。这时候如何判断最长。
最终我没有想出如何计算，在一次遍历内，如果没有完全匹配完的情况下，怎么找出最长序列。

答案解析

暴力法

找出列表中，连续的两位，四位，或者2的倍数位的子串。判断子串是否是符合标准的子串。比较并记录最大子串长度。

动态规划

我看到有人说，如果遇到”最长“这一类问题，就可以考虑使用动态规划。
动态规划这一类问题。

什么是动态规划

动态规划是一种自底向上，递归是属于自上而下。
自底向上就是从第一个开始，逐步解决问题，并找到后一个和前面几个之间存在的关系。从已知的找出未知的。类似递推公式？
在这道题里面，我觉得确实可以使用动态规划。因为后面最大的合适的括号序列，和前面的括号类型存在关系。在这道题目里面 '(' 定义为0，因为括号是需要成对出现的，所以他不会对结果产生影响。
但是当我们遇到 ‘)’ 的时候呢？我们又应该如何定义当前已经成对出现的长度是多少呢？
当我们遇到的d[n] = ')'
第一种情况：d[n-1] = '('。这样的话就可以配对成对。所以他已经成对的对数应该是在之前的对数上加一。
第二种情况：d[n-1]=')'。在这种情况下，仍需要对d[n-2]进行进一步的讨论。当d[n-2] = '(' ，d[n]=d[n−1]+d[n−d[n−1]−2]+2，前一个的数值加上当前位置往前匹配d[n-1]+2个括号的数值，最后再加上二，加上。d[n-2] = ')'。但是同时我们需要继续往前检测，找到最开始配对的那一个元素，看他之前存在的是什么样的括号。然后在做计算。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        maxans = 0
        n = len(s)
        if (n == 0): return 0;
        
        dp = [0]*n        
        for i in range(n):
            if (s[i] == ')'): 
                if (s[i - 1] == '(') :
                    if i >=2:
                        dp[i] = dp[i-2]+2
                    elif i == 1:
                        dp[i] = 2
                elif (i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '('): #排除()()())这种情况，并且只有前面有一个多余的左括号才能成对。
                    if (i - dp[i - 1]) >= 2: #判断是否有需要往前再找元素
                        dp[i] = dp[i - 1] + 2 +dp[i - dp[i - 1] - 2]
                    else:
                        dp[i] = dp[i - 1] + 2                
                maxans = max(maxans, dp[i]);

        return maxans;

时间复杂度： O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。

空间复杂度： O(n)。我们需要一个大小为 n 的 dp 数组。

其实就算答案摆在我的面前我还是有点不太能理解其中的缘由，尤其是为什么不需要再考虑更早之前的括号的顺序。。

栈

很早之前就知道可以利用栈来判断子串的合理性，但是这题需要再同时找到最大的合理子串的长度。
对于遇到的每个 ‘(’ ，我们将它的下标放入栈中
对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新「最后一个没有被匹配的右括号的下标」
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        maxans = 0;
        stack = []
        stack.append(-1);
        top = 0
        for i in range(len(s)):
            if (s[i] == '('):
                stack.append(i);
                top+=1
            else:
                stack.pop();
                top-=1
                if not(bool(stack)):
                    stack.append(i);
                    top+=1
                else: 
                    maxans = max(maxans, i - stack[top]); #每次都进行判断并比较保留最大的长度
        return maxans;

时间复杂度： O(n)，n 是给定字符串的长度。我们只需要遍历字符串一次即可。

空间复杂度： O(n)。栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n) 。

不用额外的存储空间

正序，倒序分别来遍历一次。
第一次遍历中：由于是左右括号，无论怎么匹配，只要右括号的数量小于左括号，就有可能会被匹配成功。所以就可以一直循环下去，一旦出现右括号大于左括数量的情况就清空。但是如果单一只进行一侧的循环，会因为后面没有匹配完全。导致没有统计到稍后的一些子串。
第二次遍历则正好相反，倒序进行。来弥补只循环一次的漏洞。因为他们只会存在一种情况，要么左括号多，要么右括号多。两次循环则完美的包含了两种情况

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        left = 0
        right = 0
        maxlength = 0
        for i in range(n):
            if (s[i] == '('):
                left+=1;
            else:
                right+=1;
                
            if (left == right):
                maxlength = max(maxlength, 2 * right);
            elif (right > left):
                left = 0
                right = 0;
                
        left = right = 0;
        for i in range(n-1,-1,-1):
            if (s[i] == '('):
                left+=1;
            else:
                right+=1;
        
            if (left == right):
                maxlength = max(maxlength, 2 * left);
            elif (left > right):
                left = 0
                right = 0;
            
        return maxlength;

时间复杂度： O(n)，其中 nn 为字符串长度。我们只要正反遍历两边字符串即可。

空间复杂度： O(1)。我们只需要常数空间存放若干变量。

总结

动态规划，可以用来找最长或最佳解。
有时候会主动先往数据结构里面添加点元素，如链表增加头。来满足使用和后面相同的逻辑。
有很多题目变得能要求不是用多余的空间或时间就不是用多余的空间或时间。

题目和答案来自中国站力扣和美国站leetcode，仅供学习交流