每天一道算法:生成有效括号字符串

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实现

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20181022G0SSSE00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券