给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
时间: 2023-03-28 07:03:02 浏览: 154
我可以回答这个问题。这个问题可以使用栈来解决。我们可以遍历字符串,如果遇到左括号,就将其下标入栈;如果遇到右括号,就将栈顶元素出栈,表示匹配成功,计算当前子串长度。如果栈为空,表示当前右括号没有匹配的左括号,将当前右括号下标入栈,继续遍历。最后栈中剩余的下标表示没有匹配的左括号,我们可以根据相邻下标之间的距离计算最长有效括号子串的长度。
相关问题
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
以下是Python的实现代码:
```python
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
if n == 0:
return 0
dp = [0] * n
res = 0
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
dp[i] = dp[i - 2] + 2
elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
res = max(res, dp[i])
return res
```
给你一个包含 '(' 和 ')'和任意字符 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 *代表任意一个字符包括有效括号 "(" 和 ")"" 示例 1: 输入:s = "(()a" 输出:2 解释:最长有效括号子串是 "()" 示例 2: 输入:s = ")*)()b)" 输出:4 解释:最长有效括号子串是 "*)()"
这是一个比较经典的括号匹配问题,可以使用栈来解决。具体思路如下:
1. 定义一个栈,用于存储左括号的下标。
2. 遍历字符串,如果遇到左括号,则将其下标入栈。
3. 如果遇到右括号,则弹出栈顶元素,表示匹配成功。如果此时栈为空,则说明当前右括号没有匹配的左括号,需要将当前右括号的下标入栈作为新的起点。
4. 每次弹出栈顶元素时,更新最长有效括号子串的长度,即为当前下标减去栈顶元素下标再加一。
5. 遍历完成后,如果栈不为空,则还需要根据栈中元素所表示的下标计算最长有效括号子串的长度。
具体实现可以参考以下代码:
```python
def longestValidParentheses(s):
stack = [-1] # 栈底元素,表示当前有效括号子串的起点
max_len = 0
for i, c in enumerate(s):
if c == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
max_len = max(max_len, i - stack[-1])
return max_len
```
需要注意的是,题目中给出的字符串中可能包含任意字符,而不仅仅是左右括号。因此,我们需要对遍历过程中遇到的非括号字符进行忽略,不影响括号匹配。
阅读全文