22、生成有效括号字符串
题目
给定整数n,要求输出 n 对左右括号的所有可能的有效组合。
示例:
思路
为了保证括号字符串是有效的,需要满足两个条件:
1、左括号必须有同样类型的右括号相匹配
2、右括号匹配顺序必须和左括号相对应
详情可以参考
每天一道算法:判断有效括号
。
可以使用递归法,来保证这两个条件,步骤如下:
1、起始有 n 个左括号和 n 个右括号需要拼接到字符串中。
2、先将结果字符串初始化为空。
3、每次递归时,选择其中一种括号,拼接到结果字符串的最右边。分为两种情况:
(1)如果剩余左括号和右括号的数量相等,那么下一步只能放左括号
(2)如果剩余右括号多于左括号,那么既可以放左括号,又可以放右括号
不可能出现左括号多于右括号的情况。
4、直至没有剩余括号为止。
比如:需要放两对括号,则
1、首先,只能放左括号,结果为'('
2、现在剩下 1 个左括号和 2 个右括号,因此两个都可以放,结果为 '()' 和 '(('
3、现在结果集有两种情况了,
(1)对于 '()',还剩下各1种括号,因此只能放左括号,得到 '()('
(2)对于 '((',还剩下2个右括号,因此既可以放左又可以放右,但是左括号剩余0个,因此只能放右括号,得到 '(()'
4、将最后一个剩余的字符拼接上去,得到 '()()' 和 '(())'
代码
python实现
领取专属 10元无门槛券
私享最新 技术干货