中国建设银行的网站设计,地下城做心悦任务的网站,合肥营销型网站,用vs2008做的网站前台脚本是什么题目
给你一个只包含 ( 和 ) 的字符串#xff0c;找出最长有效#xff08;格式正确且连续#xff09;括号子串的长度。
示例 示例 1#xff1a; 输入#xff1a;s (()
输出#xff1a;2
解释#xff1a;最长有效括号子串是 ()示例 2#xf…题目
给你一个只包含 ( 和 ) 的字符串找出最长有效格式正确且连续括号子串的长度。
示例 示例 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] 结尾的最长有效括号子串的长度vectorint 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;}
};
