力扣hot100 最长有效括号 动态规划
Problem: 32. 最长有效括号
思路
👨🏫 参考题解
Code
⏰ 时间复杂度:
O
(
n
)
O(n)
O(n)
🌎 空间复杂度:
O
(
n
)
O(n)
O(n)
class Solution {
public int longestValidParentheses(String s)
{
int n = s.length();
int[] f = new int[n];// f[i] 表示以第 i 个字符结尾的最长有效子字符串的长度
int ans = 0;
for (int i = 1; i < n; i++)
{
if (s.charAt(i) == ')')// 只有右括号结尾才有效
if (s.charAt(i - 1) == '(')// 上一个是 左括号
{
if (i < 2)
f[i] = 2;
else
f[i] = f[i - 2] + 2;
} else // 上一个也是 右括号
{
if (f[i - 1] > 0) //前面已经组成有效括号对序列
{
int pre = i - 1 - f[i - 1]; // 此处 s[pre] 与 s[i] 是相配对的位置
if (pre >= 0 && s.charAt(pre) == '(')// 存在且配对成功
{
f[i] = f[i - 1] + 2;// 在前边的 f[i-1] 上再加上一对
if (pre - 1 > 0)//看看 pre 前边是否还有已经配对好的序列
f[i] += f[pre - 1];
}
}
}
ans = Math.max(ans, f[i]);//更新答案
}
return ans;
}
}
原文地址：https://blog.csdn.net/lt6666678/article/details/135708673
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！