括号匹配
重要性质：如果当前遍历到的左括号的数目严格小于右括号的数目则表达式无效。
动态规划
dp(i,j)表示i是否合法，
dp(i)表示i开头的最长有效括号长度
栈
左括号一个栈，* 号一个栈，栈存的是元素位置
遇到右括号 优先左括号，否则* 号。
最后注意把剩余左括号 找位置右边的* 号当右括号匹配。
贪心
维护左括号最大数量和最小数量，看能否是0
注意： 任何情况下，未匹配的左括号数量必须非负。
如果遇到左括号，则未匹配的左括号数量加 11；
如果遇到右括号，则需要有一个左括号和右括号匹配，因此未匹配的左括号数量减 11；
如果遇到星号，由于星号可以看成左括号、右括号或空字符串，因此未匹配的左括号数量可能加 1、减 1或不变。
minCount = max(minCount - 1, 0);
应用
设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
'''
穷举2^n, 每次增加(或者)，都从右边加，要去掉不合法的，不合法定义：当前rightCount> leftCount.
:param n:
:return:
'''
res = []
def backtrack(left, right, cur=""):
if left < 0 or right < 0 or left>right:
return
if left == 0 and right == 0:
res.append(cur)
# 加左括号
if left > 0:
backtrack(left - 1, right,cur+"(")
if right > 0:
backtrack(left, right - 1, cur + ")")
backtrack(n, n, "")
return res
判断是否有效的括号表达式，用栈即可。20. 有效的括号
判断有效括号同时增加了*，应该是动态规划。678. 有效的括号字符串
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号
(必须有相应的右括号)。 - 任何右括号
)必须有相应的左括号(。 - 左括号
(必须在对应的右括号之前)。 *可以被视为单个右括号)，或单个左括号(，或一个空字符串。- 一个空字符串也被视为有效字符串。
class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
}
32. 最长有效括号 给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 动态规划
class Solution:
def longestValidParentheses(self, s: str) -> int:
res = 0
dp = [0 for _ in range(len(s) + 1)]
for i in range(len(s) - 2, -1, -1):
if s[i] == "(":
j = i + dp[i + 1] + 1
if j < len(s) and s[j] == ")":
dp[i] = dp[i + 1] + 2
if j + 1 < len(s):
dp[i] += dp[j + 1]
res = max(res, dp[i])
return res