周末刷一下算法题，刚好遇到一道有趣的匹配子串问题。原题描述如下：
给定一个只包含字符 '(' 和 ')' 的字符串，返回其中 最长的有效（格式正确的）括号子串的长度。示例 1：
输入：s = "(()"
输出：2
解释：最长的有效括号子串是 "()"。示例 2：
输入：s = ")()())"
输出：4
解释：最长的有效括号子串是 "()()"。示例 3：
输入：s = ""
输出：0约束条件：
0 <= s.length <= 3 * 10⁴s[i] 仅为 '(' 或 ')'。
先想到用一个栈记录左括号“（”和右括号“）”来维护不匹配括号的位置，后面再思考了一下这个算法不够优秀，完全可以把这个问题变成一个简单的数学归纳问题。从左往右匹配一遍，再从右往左匹配一遍，这样才不会遗漏所有的匹配子串。
用Python实现起来非常方便，代码如下所示：
class Solution:def longestValidParentheses(self, s: str) -> int:max_len = 0left = right = 0# Left to right scan itfor char in s:if char == '(':left += 1else:right += 1if left == right:max_len = max(max_len, 2 * right)elif right > left:left = right = 0# Right to left scan itleft = right = 0for char in reversed(s):if char == ')':right += 1else:left += 1if left == right:max_len = max(max_len, 2 * left)elif left > right:left = right = 0return max_len
其实在max_len = max(max_len, 2 * left）或者 max_len = max(max_len, 2 * right）都是一样的，因为这个时候都是left等于right，但出于自然理解的逻辑才写成如上所示。还可以考虑用动态规划的方法来解决这个问题，但空间复杂度也会更高。
多思考，多写代码，防止中年摆烂。