周末刷一下算法題，剛好遇到一道有趣的匹配子串問題。原題描述如下：

給定一個只包含字符 '(' 和 ')' 的字符串，返回其中 最長的有效（格式正確的）括號子串的長度。

示例 1：
輸入：s = "(()"
輸出：2
解釋：最長的有效括號子串是 "()"。

示例 2：
輸入：s = ")()())"
輸出：4
解釋：最長的有效括號子串是 "()()"。

示例 3：
輸入：s = ""
輸出：0

約束條件：
0 <= s.length <= 3 * 10?

s[i] 僅為 '(' 或 ')'。

先想到用一個棧記錄左括號“（”和右括號“）”來維護不匹配括號的位置，后面再思考了一下這個算法不夠優(yōu)秀，完全可以把這個問題變成一個簡單的數(shù)學歸納問題。從左往右匹配一遍，再從右往左匹配一遍，這樣才不會遺漏所有的匹配子串。
用Python實現(xiàn)起來非常方便，代碼如下所示：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        max_len = 0
        left = right = 0
        # Left to right scan it
        for char in s:
            if char == '(':
                left += 1
            else:
                right += 1
            if left == right:
                max_len = max(max_len, 2 * right)
            elif right > left:
                left = right = 0

        # Right to left scan it
        left = right = 0
        for char in reversed(s):
            if char == ')':
                right += 1
            else:
                left += 1
            if left == right:
                max_len = max(max_len, 2 * left)
            elif left > right:
                left = right = 0
      
        return max_len

其實在max_len = max(max_len, 2 * left）或者 max_len = max(max_len, 2 * right）都是一樣的，因為這個時候都是left等于right，但出于自然理解的邏輯才寫成如上所示。還可以考慮用動態(tài)規(guī)劃的方法來解決這個問題，但空間復雜度也會更高。
多思考，多寫代碼，防止中年擺爛。