LeetCode Longest Valid Parentheses：動態規劃 O(n) 解法詳解

題目回顧

給定只含 '(' 和 ')' 的字符串，找最長合法括號子串長度。
例："(()" → 2；")()())" → 4

DP 狀態定義

dp[i]：以 i 結尾的最長合法子串長度。
最終答案 = max(dp)。

遞推邏輯

只考慮 s[i] == ')' 的情況（以 '(' 結尾不可能合法）。

1. 若 s[i-1] == '('：形成 "()"，dp[i] = dp[i-2] + 2
2. 若 s[i-1] == ')' 且 s[i - dp[i-1] - 1] == '('：前一個合法子串前面有匹配的 '('，dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]

Python 代碼

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0: return 0
        dp = [0] * n
        for i in range(1, n):
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = (dp[i-2] if i >= 2 else 0) + 2
                else: # s[i-1] == ')'
                    j = i - dp[i-1] - 1
                    if j >= 0 and s[j] == '(':
                        dp[i] = dp[i-1] + 2 + (dp[j-1] if j >= 1 else 0)
        return max(dp)

測試用例

assert Solution().longestValidParentheses("(()))())(") == 4
assert Solution().longestValidParentheses("(()") == 2
assert Solution().longestValidParentheses(")()())") == 4
assert Solution().longestValidParentheses("") == 0
assert Solution().longestValidParentheses("()(()") == 2

複雜度

• 時間：O(n)
• 空間：O(n)

其他解法

• 棧：存儲索引，遇到匹配彈出計算長度
• 雙向掃描：左右各掃一次計數左右括號，相等時更新答案