【LeetCode 热题 100】32. 最长有效括号——（解法二）动态规划
Problem: 32. 最长有效括号
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)
整体思路
这段代码同样旨在解决 “最长有效括号” 问题，但它采用的是一种 动态规划 (Dynamic Programming) 的方法。这种方法通过构建一个DP表（dp 数组），从左到右逐步计算以每个字符为结尾的最长有效括号子串的长度。
算法的核心在于定义状态 dp[i] 并找出其状态转移关系。
-
状态定义：
dp[i]被定义为：以字符串s中第i-1个字符（即s.charAt(i-1)）为结尾的最长有效括号子串的长度。- 索引偏移：为了方便处理边界，代码在原始字符串
s前面加了一个空格" "，使得s的索引从1开始。这样，dp数组的索引i就直接对应了新字符串的索引i。
-
状态转移方程：
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]]。
- 新形成的这个大括号
- 如果
-
最终结果：
- 在填充
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)
- 字符串拼接：
s = " " + s;在Java中会创建一个新的字符串，这需要 O(N) 的时间。 - 循环：算法的核心是一个
for循环，它从i = 2遍历到s.length() - 1。这个循环严格地执行N-1次（N为原字符串长度）。 - 循环内部操作：
- 在循环的每一次迭代中，执行的都是常数次的操作：字符访问
charAt()、数组访问dp[]、加减法和Math.max。 - 这些操作的时间复杂度都是 O(1)。
- 在循环的每一次迭代中，执行的都是常数次的操作：字符访问
综合分析：
算法的总时间复杂度是 O(N) (字符串拼接) + O(N) (循环) = O(N)。
空间复杂度：O(N)
- 主要存储开销：
String s = " " + s;: 创建了一个新的字符串对象，其长度为N+1，占用了 O(N) 的空间。int[] dp = new int[s.length()]: 创建了一个dp数组，其长度也为N+1，占用了 O(N) 的空间。
综合分析：
算法所需的额外空间主要由新的字符串对象和 dp 数组决定。因此，其空间复杂度为 O(N)。