括号问题

2023-09-17

括号是一类有趣的问题，主要与有效括号相关，例如：

  1. 检查字符串是否是有效括号
  2. 在子串中找到最长的有效括号（子串）
  3. 在子串中找到最长的有效括号（子序列）
  4. 为给定长度生成所有有效括号
  5. …

在深入探讨每个主题之前，让我们定义什么是有效括号。()、()()()()和((((((()))))))(())()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def isValidParentheses(s: str):
    need = 0
    for ch in s:
        if ch == '(':
            need += 1
        else:
            need -= 1
            if need < 0:
                return False
    return True

def isValidParentheses(s: str):
    stack = []
    for ch in s:
        if ch == ')':
            if stack[-1] == '(':
                stack.pop()
            else:
                stack.append(ch)
        else:
            stack.append(ch)