題目

給你一個只包含?'('?和?')'?的字符串，找出最長有效（格式正確且連續）括號子串的長度。

示例

示例 1：

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

示例 2：

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

示例 3：

輸入：s = ""
輸出：0

分析

可以使用動態規劃的方法來解決這個問題。我們定義一個數組?dp，其中?dp[i]?表示以?s[i]?結尾的最長有效括號子串的長度。

動態規劃

代碼解釋

初始化：n?為字符串?s?的長度。dp?數組初始化為 0，長度為?n。maxLength?用于記錄最長有效括號子串的長度，初始化為 0。

動態規劃過程：

• 遍歷字符串?s，從第二個字符開始（因為第一個字符不可能組成有效括號子串）。
• 如果當前字符是?)：
  • 情況一：如果前一個字符是?(，則可以與前一個字符組成一對有效括號。此時?dp[i]?等于?dp[i - 2]（如果?i >= 2）加上 2。
  • 情況二：如果前一個字符也是?)，則需要檢查更前面的字符是否能組成有效括號。如果?i - dp[i - 1] > 0?且?s[i - dp[i - 1] - 1] == '('，則?dp[i]?等于?dp[i - 1]?加上?dp[i - dp[i - 1] - 2]（如果?i - dp[i - 1] >= 2）再加上 2。
• 更新?maxLength?為?dp[i]?和?maxLength?中的較大值。

返回結果：

• 最后返回?maxLength，即最長有效括號子串的長度。

時間復雜度：O()，?是字符串的長度

空間復雜度：O()

class Solution {
public:int longestValidParentheses(string s) {int n = s.length();if (n == 0) return 0;// dp[i] 表示以 s[i] 結尾的最長有效括號子串的長度vector<int> dp(n, 0);int maxLength = 0;for (int i = 1; i < n; ++i) {if (s[i] == ')') {if (s[i - 1] == '(') {// 如果當前字符是 ')' 且前一個字符是 '('，則可以與前一個字符組成一對有效括號dp[i] = (i >= 2? dp[i - 2] : 0) + 2;} else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {// 如果當前字符是 ')' 且前一個字符也是 ')'，則需要檢查更前面的字符是否能組成有效括號dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2? dp[i - dp[i - 1] - 2] : 0) + 2;}maxLength = max(maxLength, dp[i]);}}return maxLength;}
};