括号生成（中等）（leetcode22）
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
思路：每次增加括号时需要判断之前字符串中左右括号的个数，判断增加‘(’或‘)’依据为，若之前字符串中左括号个数小于n，则应增加左括号，若之前字符串中右括号个数小于左括号，则应增加右括号
def generateParenthesis(self, n):
result=[]
def trackback(s,left,right):
if len(s)==2*n:
result.append(s)
if left<n: #加左括号
trackback(s+'(',left+1,right)
if right<left: #加右括号
trackback(s+')',left,right+1)
trackback("",0,0)
return result
有效的括号（简单）（leetcode20）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例1: 输入: "()" 输出: true
示例 2: 输入: "()[]{}" 输出: true
示例 3: 输入: "(]" 输出: false
示例 4: 输入: "([)]" 输出: false
示例 5: 输入: "{[]}" 输出: true
def isValid(self, s):
a={')':'(',']':'[','}':'{'}
l=[None]
for i in s:
if i in a and a[i]==l[-1]:
l.pop()
else:
l.append(i)
return len(l)==1
最长有效括号（困难）（leetcode32）
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1: 输入: "(()" 输出: 2
解释: 最长有效括号子串为 "()"
示例 2: 输入: ")()())" 输出: 4
解释: 最长有效括号子串为 "()()"
def longestValidParentheses(self, s):
s=')'+s # dp表示到该字符处的最长有效括号长度
dp=[0]*len(s)
for i in range(1,len(s)):
if s[i]==')': # 只有右括号时才可能有效
if s[i-1-dp[i-1]]=='(': # 如果dp[i-1]范围前一个字符为左括号
dp[i]=dp[i-1]+2
dp[i]+=dp[i-dp[i]] # 加上dp[i]范围前一个字符的dp
return max(dp)