Problem: 32. 最長有效括號

整體思路

這段代碼同樣旨在解決 “最長有效括號” 問題，但它采用的是一種 動態規劃 (Dynamic Programming) 的方法。這種方法通過構建一個DP表（dp 數組），從左到右逐步計算以每個字符為結尾的最長有效括號子串的長度。

算法的核心在于定義狀態 dp[i] 并找出其狀態轉移關系。

1. 狀態定義：

   • dp[i] 被定義為：以字符串 s 中第 i-1 個字符（即 s.charAt(i-1)）為結尾的最長有效括號子串的長度。
   • 索引偏移：為了方便處理邊界，代碼在原始字符串 s 前面加了一個空格 " "，使得 s 的索引從1開始。這樣，dp 數組的索引 i 就直接對應了新字符串的索引 i。

2. 狀態轉移方程：

   • dp[i] 的值只有在 s.charAt(i) 是一個右括號 ')' 時才可能大于0，因為一個有效的括號子串必然以 ')' 結尾。如果 s.charAt(i) 是 '('，dp[i] 默認為0。
   • 當 s.charAt(i) == ')' 時，我們需要尋找一個與之匹配的左括號 '('。這里有兩種主要情況：
     a. 情況 1：形如 ...()
     • 如果 s.charAt(i-1) 是一個 '('，那么 s.charAt(i) 和 s.charAt(i-1) 構成了最簡單的一對有效括號 ()。
     • 這個 () 的長度是 2。它還可以連接在 s.charAt(i-2) 結尾的有效子串后面。
     • 因此，狀態轉移方程為：dp[i] = dp[i-2] + 2。
       b. 情況 2：形如 ...))
     • 如果 s.charAt(i-1) 也是一個 ')'，那么 s.charAt(i) 需要去匹配更左邊的某個 '('。
     • 我們知道，以 s.charAt(i-1) 結尾的有效子串長度是 dp[i-1]。那么，這個子串的起始位置就是 i - 1 - dp[i-1] + 1。它所需要匹配的左括號就在這個起始位置的前一個，即索引 i - 1 - dp[i-1] 的位置。
     • 我們檢查 s.charAt(i - 1 - dp[i-1]) 是否為 '('。
     • 如果匹配成功：
       • 新形成的這個大括號 (...) 的長度是 dp[i-1] + 2。
       • 并且，這個大括號還可以連接在它前面的另一個有效子串后面。這個“前面的有效子串”是以 s.charAt(i - 2 - dp[i-1]) 結尾的，其長度為 dp[i - 2 - dp[i-1]]。
       • 因此，總長度為：dp[i] = dp[i-1] + 2 + dp[i - 2 - dp[i-1]]。

3. 最終結果：

   • 在填充 dp 數組的過程中，dp[i] 只是以 s.charAt(i) 為結尾的最長長度。全局的最長長度可能是任何一個 dp[i] 的值。
   • 因此，需要一個 ans 變量來實時記錄并更新所有 dp[i] 中的最大值。

完整代碼

class Solution {/*** 找到字符串中最長的有效括號子串的長度。* @param s 只包含 '(' 和 ')' 的字符串* @return 最長有效括號子串的長度*/public int longestValidParentheses(String s) {// ans: 用于存儲全局的最長有效括號子串長度。int ans = 0;// 技巧：在 s 前面加一個空格，使得索引從 1 開始，方便處理邊界情況 dp[i-2]。s = " " + s;// dp 數組：dp[i] 表示以 s.charAt(i) 結尾的最長有效括號子串的長度。int[] dp = new int[s.length()];// 從索引 2 開始遍歷，因為最短的有效括號 "()" 長度為 2。for (int i = 2; i < s.length(); i++) {// 只在遇到右括號時才可能形成有效子串if (s.charAt(i) == ')') {// 情況 1: 子串形如 ".....()"if (s.charAt(i - 1) == '(') {// 長度 = 前面有效子串的長度 (dp[i-2]) + "()" 的長度 (2)dp[i] = dp[i - 2] + 2;} // 情況 2: 子串形如 ".....))"// 且 s.charAt(i-1) 結尾的子串是有效的 (dp[i-1] > 0)// 我們需要檢查 s[i-1-dp[i-1]] 是否是與之匹配的'('else if (i - 1 - dp[i - 1] > 0 && s.charAt(i - 1 - dp[i - 1]) == '(') {// 長度 = s[i-1]結尾的子串長度 + 新匹配的"()"長度 + 更前面連接的有效子串長度dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i-1]];}}// 每次計算完 dp[i]后，都用它來更新全局最大值 ans。ans = Math.max(ans, dp[i]);}return ans;}
}

時空復雜度

時間復雜度：O(N)

1. 字符串拼接：s = " " + s; 在Java中會創建一個新的字符串，這需要 O(N) 的時間。
2. 循環：算法的核心是一個 for 循環，它從 i = 2 遍歷到 s.length() - 1。這個循環嚴格地執行 N-1 次（N 為原字符串長度）。
3. 循環內部操作：
   • 在循環的每一次迭代中，執行的都是常數次的操作：字符訪問 charAt()、數組訪問 dp[]、加減法和 Math.max。
   • 這些操作的時間復雜度都是 O(1)。

綜合分析：
算法的總時間復雜度是 O(N) (字符串拼接) + O(N) (循環) = O(N)。

空間復雜度：O(N)

1. 主要存儲開銷：
   • String s = " " + s;: 創建了一個新的字符串對象，其長度為 N+1，占用了 O(N) 的空間。
   • int[] dp = new int[s.length()]: 創建了一個 dp 數組，其長度也為 N+1，占用了 O(N) 的空間。

綜合分析：
算法所需的額外空間主要由新的字符串對象和 dp 數組決定。因此，其空間復雜度為 O(N)。