最长的括号子串
问题描述
给出一个长度为 n 的，仅包含字符 ‘(‘ 和 ‘)’ 的字符串，计算最长的格式正确的括号子串的长度。
示例：
输入：”(())”
输出：4
解析：对于”(())”来说，最长格式正确的子串是”(())”，所以为4。
分析问题
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:67094d9f-297a-49cb-bff8-c1ea91e39889
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:688a37f8-e0cd-40ee-aea9-60d9245e208d
- 如果遇到的是左括号’（’，我们就把它的下标放入栈中；
- 如果遇到的是右括号’）’，此时有两种情况；
- 如果此时栈为空，说明当前的右括号是没有被匹配的右括号，
- 如果此时栈不为空，右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」，然后用它来更新最大值即可。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:89b84fad-a6bd-497a-854f-eb30e8889aa7
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:bd307f16-db72-4d48-8011-ec538337dd90
我们以”())(())”为例，来看一下执行过程。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ced6779d-b97f-4848-b78b-5884431690bc
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:65cbe630-f30f-4661-8d37-98ff7e6a7731
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)。
动态规划解法
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:9d25f7df-85b4-4182-9687-73fbbd41460e
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5db85e63-a7a6-4ba5-8b1e-38c2c120decf
首先我们定义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)”前面的有效子串的长度，我们需要加上。
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ee023471-2029-48f5-af7e-8abf9b40c116
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e4ad8ca5-b7e6-4531-a77e-521bbad6bd50
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)。
Original: https://www.cnblogs.com/cxyxz/p/15570944.html
Author: 算法推荐管
Title: 阿里二面算法题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/562429/
转载文章受原作者版权保护。转载请注明原作者出处！