最长的括号子串
最长的括号子串
问题描述
给出一个长度为 n 的，仅包含字符 ‘(‘ 和 ‘)’ 的字符串，计算最长的格式正确的括号子串的长度。
示例：
输入：”(())”
输出：4
解析：对于”(())”来说，最长格式正确的子串是”(())”，所以为4。
分析问题
对于括号匹配问题，最直观的想法就是采用栈来求解。所以，我们也可以采用栈来求解这道题。具体来说，我们在遍历给定字符串的过程中，需要始终保证栈底元素为当前已经遍历过的元素中，最后一个没有被匹配的右括号的下标，栈中的其它元素维护左括号的下标。
- 如果遇到的是左括号‘（’，我们就把它的下标放入栈中；
- 如果遇到的是右括号‘）’，此时有两种情况；
- 如果此时栈为空，说明当前的右括号是没有被匹配的右括号，
- 如果此时栈不为空，右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」，然后用它来更新最大值即可。
这里需要注意一点，因为一开始栈为空，如果此时第一个字符为左括号时，我们会将其对应的下标放入栈中，这样就不满足栈底始终保存的是最后一个没有被匹配的右括号的下标这个条件，为了保证该条件成立，我们在开始时需要往栈中放入一个元素-1。
我们以“())(())”为例，来看一下执行过程。
下面我们来看一下代码实现。
class Solution(object):
def longestValidParentheses(self, s):
stack=[]
n=len(s)
stack.append(-1)
maxlen=0
for i in range(0,n):
#如果是左括号，将其对应的下标加入栈中
if s[i]=='(':
stack.append(i)
else:
#如果是右括号，栈顶元素pop出去
stack.pop()
if not stack:
stack.append(i)
else:
maxlen = max(maxlen, i - stack[-1])
return maxlen
该算法的时间复杂度和空间复杂度都是O(n)。
动态规划解法
对于求最优解问题，我们一般首先需要考虑的就是动态规划的解法。显然，求最长的括号子串是最优解问题，所有我们也可以采用动态规划的思想来求解。
首先我们定义dp[i]表示以下标i字符结尾的最长有效括号的长度，初始时数组dp全为0。对于有效的括号子串来说，显然是以字符‘）’结尾的，因此我们可以知道以‘（’结尾的子串对应的dp值必然为0，所以我们只需要求解字符‘）’在dp数组中对应位置的值即可。
我们从前往后遍历字符串s。
-
如果s[i]=‘）’且 s[i-1]=‘（’，也就是字符串是 “….()….()….”的形式，那么我们可以得出状态转移方程为dp[i] = dp[i-2] + 2。
-
如果s[i]=‘）’且 s[i-1]=‘）’，也就是字符串是“………))…”的形式，此时如果s[i-dp[i-1]-1] = ‘（’，那么
dp[i] = dp[i-1] + 2 + dp[i – dp[i-1] – 2]
解释：如果 s[i-1] 对应的 ‘）’ 是有效子字符串的一部分，我们假设为sub1，那么它的的长度为dp[i-1]，如果s[i]对应的‘）’是一个更长子字符串的一部分，那么一定有一个对应的‘（’与子相匹配，且它的位置在sub1的之前。如果sub1的前面恰好是‘（’，即“ (sub1) ”的形式，那么dp[i]=dp[i-1] + 2 + dp[i-dp[i-1] – 2] ，其中dp[i-dp[i-1] – 2] 表示字符串“(sub1)”前面的有效子串的长度，我们需要加上。
下面我们来看一下代码的实现。
class Solution(object):
def longestValidParentheses(self, s):
maxlen=0
n=len(s)
dp=[0] * n
for i in range(1,n):
#如果s[i]==')'并且s[i-1]=='(',那么dp[i] = dp[i-2]+2
if s[i]==')':
if s[i-1]=='(':
dp[i] = 2 + (dp[i-2] if i>=2 else 0)
elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1]=='(':
dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i-dp[i-1]>=2 else 0)
maxlen=max(maxlen,dp[i])
return maxlen
该算法的时间复杂度是O(n)，空间复杂度也是O(n)。
