- 使用栈: 遍历字符串,当遇到左括号时,将其下标压入栈中;当遇到右括号时,如果栈为空,则将当前右括号下标作为新的起始点,否则将栈顶元素出栈,并计算当前有效括号的长度。 Python代码示例:
def longest_valid_parentheses(s):
stack = [-1] # 栈中始终保持一个起始位置
max_length = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if len(stack) == 0:
stack.append(i)
else:
max_length = max(max_length, i - stack[-1])
return max_length
- 使用动态规划: 定义一个动态规划数组 dp,其中 dp[i] 表示以索引 i 结尾的最长有效括号的长度。对于每个右括号,需要考虑其前面的字符是否是左括号,如果是,则可以与该左括号匹配,此时的最长有效括号长度为 dp[i-2] 加上 2;还需要考虑右括号前面的字符是否是右括号,如果是,则需要找到与当前右括号匹配的左括号的前一个位置 j,此时的最长有效括号长度为 dp[i-1] 加上 2 再加上 dp[j-1]。 Python代码示例:
def longest_valid_parentheses(s):
n = len(s)
dp = [0] * n
max_length = 0
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
dp[i] = dp[i - 2] + 2 if i >= 2 else 2
elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
max_length = max(max_length, dp[i])
return max_length
标签:python,max,else,括号,length,解法,stack,dp
From: https://blog.51cto.com/lzning/9254035