Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. [#20]
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
题意：判断只包含6种括号字符的串中对应的括号是否成对、嵌套是否有效。
用列表模拟先入后出的栈来判断括号是否有效，代码如下：
>>> def ValidParentheses(Parentheses): tmp, par = [], '()[]{}' for i in Parentheses: if i in par[0::2]: tmp.append(par[1::2][par[0::2].index(i)]) elif i in par[1::2]: if tmp==[]: return False elif i!=tmp[-1]: break else: tmp.pop() else: Parentheses = Parentheses[1:] return tmp==[] >>> inputPar = "()" >>> ValidParentheses(inputPar) True >>> inputPar = "()[]{}" >>> ValidParentheses(inputPar) True >>> inputPar = "(]" >>> ValidParentheses(inputPar) False >>> inputPar = "([)]" >>> ValidParentheses(inputPar) False >>> inputPar = "{[]}" >>> ValidParentheses(inputPar) True >>> >>> inputPar ='())([])' >>> ValidParentheses(inputPar) False >>> inputPar = "(3+3/7)*3+((6+2)*(6/2))" >>> ValidParentheses(inputPar) True >>> # 注：函数中用else:Parentheses = Parentheses[1:],已经可以判断不只包含括号的字符串了
Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. [#22]
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
题意：给定数字n，求出 n 对小括号组成的所有嵌套成对有效的组合。
如果不计程序的时间复杂度以及内存空间大小，用排列公式配合本文上一题目中的自定义函数判断就可搞定，代码如下：
>>> from itertools import permutations as perm >>> n = 3 >>> inputPar = (['('] + [')'])*n >>> sorted(list({''.join(i) for i in [*perm(inputPar)] if ValidParentheses(''.join(i))})) ['((()))', '(()())', '(())()', '()(())', '()()()'] >>> >>> 或者：（首先有效字串首尾肯定分别是“(”,")） >>> n = 3 >>> inputPar = (['('] + [')'])*(n-1) >>> sorted(list({'('+''.join(i)+')' for i in [*perm(inputPar)] if ValidParentheses('('+''.join(i)+')')})) ['((()))', '(()())', '(())()', '()(())', '()()()']
用以上方法n<7运行没问题；但当n=7时，python报内存错误“MemoryError”。想想14！= 87178291200
正确的解法：
>>> def GenerateParentheses(l,r,par): global res if l==0 and r==0: res.append(par) return if l>0: GenerateParentheses(l-1,r,par+'(') if r>0 and l<r: GenerateParentheses(l,r-1,par+')') >>> def ParPairs(n): global res res = [] GenerateParentheses(n,n,'') return res >>> ParPairs(3) ['((()))', '(()())', '(())()', '()(())', '()()()'] >>>
此方法直接运行 ParPairs(n) 算到n=10时也会报“MemoryError”，用个临时变量接收 t=ParPairs(n) 可以算得更多，但n越大就超慢，接近20时也就动不了了。
