动态规划<3>最长有效括号(longest-valid-parentheses )

vlambda
2020-05-14

动态规划<3>最长有效括号(longest-valid-parentheses )

本节为动态规划第三题：最长有效括号(longest-valid-parentheses )，主要包括：问题描述，算法思路，复杂度分析，C++实现。

1. 问题描述

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()”

示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

2. 解法

2.1 暴力法

即采用栈的方法，每次遇到左括号就把他放在栈顶，每次遇到右括号就从栈顶弹出一个左括号，如果栈顶不是左括号或者遍历完整个字符串后栈中仍然有元素，那么该字符串无效。这种方法中，我们对每个偶数长度的字符串都进行判断，保存目前未知找到的最长的有效子字符串长度。

//1. 暴力法：时间复杂度O(n^2),空间复杂度O(n) bool isValid(string s) { stack<char> myStack; for (int i = 0; i < s.length(); i++) { if (s.at(i) == '(') { myStack.push('('); } else if (!myStack.empty() && myStack.top() == '(') { myStack.pop(); } else return false; } return myStack.empty(); } int longestValidParentheses(string s) { int maxLen = 0; for (int i = 0; i < s.length(); i++) { for (int j = i + 2; j <= s.length(); j += 2) { if (isValid(s.substr(i, j - i))) maxLen = max(maxLen, j - i); } } return maxLen; }

2.2 暴力法改进

解法一找到每个可能的字符串后再判断它的有效性，改进版解法之遍历给定字符串一次，首先，将-1入栈，然后遇到左括号则将左括号下标入栈，遇到右括号，先弹出栈顶元素，如果此时栈为空，则将右括号下标入栈，否则，若当前右括号的下标与当前栈顶元素的差大于最大有效括号长度，则这个差作为最大有效括号长度。也就是说改进版算法不断更新最大有效括号长度为当前遍历到的子字符串的有效括号长度，直到遍历结束，也就是我们刚开始学习栈时遇到的括号匹配问题，只不过该题要求这个长度，我们做了一个特殊的处理。

//2.暴力法改进,时间复杂度O(n)，空间复杂度O(n) int longestValidParentheses(string s) { int maxLen = 0; stack<int> myStack; myStack.push(-1); for (int i = 0; i < s.length(); i++) { if (s.at(i) == '(') myStack.push(i); else { myStack.pop(); if (myStack.empty()) myStack.push(i); else maxLen = max(maxLen, i - myStack.top()); } } return maxLen; }

2.3 左右指针解法

这种方法时间复杂度O(n)，空间复杂度O(1)，但是其常数时间比较大，毕竟有舍才有得。其实这道题目没什么难度，用动态规划有一种杀鸡牛刀的感觉，但是为了体会这种思想，还是会给出第四种解法。我们先回到这种不需要额外空间的方法，这种方法首先从左到右遍历给定字符串，遇到左括号则左指针加1，遇到右括号则右指针加1，过程中，如果左右指针相等，则令maxLen为两倍的右指针数值(大于当前的maxLen)，如果出现了右指针大于做指针得情况那么遍历到目前未止得子字符串就不会有更大的有效括号长度了。但是这一过程漏掉了最长有效括号子字符串在右端的情况，所以需要再从右到左遍历给定字符串，同样遇到左括号则左指针加1，遇到右括号则右指针加1，过程中，如果左右指针相等的情况出现，令maxLen为两倍的做指针数值(若大于当前maxLen),若出现左指针大于右指针的情况，则说明遍历到目前未知的子字符串已经不可能出现比当前maxLen更大的有效括号长度了。

//3.左右指针解法，时间复杂度O(n)，空间复杂度O(1) int longestValidParentheses(string s) { int left = 0, right = 0, maxLen = 0; for (int i = 0; i < s.length(); i++) { if (s.at(i) == '(') left++; else right++;
 if (left == right) maxLen = max(maxLen, 2 * right); else if (left <= right) { left = 0; right = 0; } } left = 0; right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.at(i) == '(') left++; else right++;
 if (left == right) maxLen = max(maxLen, 2 * left); else if (left >= right) { left = 0; right = 0; } } return maxLen; }

2.4 动态规划解法

首先定义一个dp数组，其中第i个元素表示以下标i为i的字符结尾的最长有效子字符串的长度。将dp数组全部初始化为0，很明显，有效的子字符串一定以右括号结尾，进一步，有以左括号结尾的子字符串对应的dp数组位置上必定为0.所以我们只需要更新右括号在dp数组中对应位置的值。

为了求出dp数组，每两个字符检查一次，如果满足条件：

s[i]=’)‘且s[i-1]=’(’，也就是形如"…()"，我们可以推出：dp[i]=dp[i-1]+2
s[i]=’)‘且s[i-1]=’)’，也就是形如“…))”，我们可以推出若s[i-dp[i-1]-1]=’(’，则dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2。具体来看，如果倒数第二个’)‘是一个有效字符串sub_s的一部分，对于最后一个’)’，如果它是一个更长子字符串的一部分，那么它一定有一个对应的’(’，它的位置在sub_ssubs前面。因此，如果sub_s前面恰好是’(’，那么我们就用2加上sub_s的长度去更新dp[i]。除此之外，我们也需要把有效子字符串"(sub_s)"之前的有效子字符串的长度也加上，也就是加上dp[i-dp[i-1]-2]。

//4.动态规划解法，时间复杂度O(n)，空间复杂度O(n) int longestValidParentheses(string s) { int maxLen = 0; vector<int> dp(s.length()); for (int i = 1; i < s.length(); i++) { if (s.at(i) == ')') { if (s.at(i - 1) == '(') dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; else if (i - dp[i - 1] > 0 && s.at(i - dp[i - 1] - 1) == '(') dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2; maxLen = max(maxLen, dp[i]); } } return maxLen; }