用python中类和对象的知识编写:输入一组字符串,已知所给字符串只包含“(”和“)”,请使用顺序查找,求出最长的合法括号子串的长度。例如所给字符串为()()()),则最长的合法括号子串为()()(),因此输出该子串的长度6。 输入:()()() 输出:6
时间: 2024-01-03 19:04:01 浏览: 150
好的,这个问题可以使用栈来解决。我们可以定义一个栈,然后遍历输入的字符串,遇到左括号就将其压入栈中,遇到右括号就弹出栈顶元素,如果栈顶元素是左括号,则表明这是一个合法的括号子串,计算该子串的长度,并更新最长长度。具体实现可以参考以下代码:
```python
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1] # 栈中初始加入一个-1,方便后续计算长度
max_len = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if not stack:
# 如果栈已经为空,表明当前右括号没有匹配的左括号,将右括号的下标加入栈中
stack.append(i)
else:
# 计算当前的合法括号子串长度,并更新最长长度
max_len = max(max_len, i - stack[-1])
return max_len
```
在上述代码中,我们使用一个`stack`列表来模拟栈的操作,如果遇到左括号,就将其下标加入栈中;如果遇到右括号,就从栈中弹出栈顶元素,如果栈为空,则将右括号的下标加入栈中,否则计算当前的合法括号子串长度并更新最长长度。最后返回最长长度即可。
这个算法的时间复杂度为$O(n)$,空间复杂度也为$O(n)$,其中$n$为输入字符串的长度。
阅读全文