一、题目
1、算法题目
“给定一个字符串，找出最长有效的字符串的长度。”
题目链接：
来源：力扣（LeetCode）
链接：32. 最长有效括号 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1： 输入： s = "(()" 输出： 2 解释： 最长有效括号子串是 "()" 复制代码
示例 2： 输入： s = ")()())" 输出： 4 解释： 最长有效括号子串是 "()()" 复制代码
二、解题
1、思路分析
这个题可以使用动态规划思路解题。
定义dp[i]表示以下标i字符结束的最长有效字符串长度，因此左括号在dp中的值必定为0，那么只需要知道右括号在dp数组中的位置。
遍历字符串求解dp值，每两个字符检查一次，如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 subs ），对于最后一个 ‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 subs 的前面）。因此，如果子字符串 subs 的前面恰好是 ‘(’ ，那么我们就用 2 加上 subs 的长度（dp[i−1]）去更新 dp[i]。同时，我们也会把有效子串 “(subs )” 之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]。
最后的答案即为 dp 数组中的最大值。
2、代码实现
代码参考：
public class Solution { public int LongestValidParentheses(string s) { int left = 0, right = 0, ans = 0; int n = s.Length; for (int i = 0; i < n; i++) { if (s[i] == '(') left++; else right++; if (left == right) ans = Math.Max(ans, right); else if (right > left) left = right = 0; } left = right = 0; for (int i = n-1; i >=0; i--) { if (s[i] == '(') left++; else right++; if (left == right) ans = Math.Max(ans, left); else if (left > right) left = right = 0; } return ans * 2; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n为字符串的长度，只需要遍历一遍字符串即可求出dp数组。
空间复杂度： O(n)
我们需要一个大小为n的dp数组。
三、总结
这道题很适合用动态规划来解题，因为有最长这个字眼，用动态规划解这道题，需要先确定状态。
然后根据状态转移方程，根据初始条件和边界去实现过程。
需要注意的是计算顺序。
