python基础编程100例：第97期-基础结构：字符串 括号生成
本文讲述了python基础编程100例：第97期-基础结构：字符串 括号生成 具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:
第97期-基础结构：字符串 括号生成
1.问题描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1:
输入: n = 3
输出: ["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入: n = 1
输出: ["()"]
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
#在此之间填写代码
print(Solution().generateParenthesis(3))
print(Solution().generateParenthesis(1))
2.解题思路
- 标签：字符串
- 当前左右括号都有大于 0 个可以使用的时候，才产生分支；
- 产生左分支的时候，只看当前是否还有左括号可以使用；
- 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
- 在左边和右边剩余的括号数都等于 0 的时候结算。
3.解题方法
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
a=[]
b=''
def x(b,i,j):
if i==j==n:a.append(b[:])
if i<j:return
if i<=n:
x(b+'(',i+1,j)
if j<=n:
x(b+')',i,j+1)
x(b,0,0)
return a
print(Solution().generateParenthesis(3))
print(Solution().generateParenthesis(1))
第1-3，16-17行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义空列表a用于存放结果
第5行： 定义空字符串b用于表示每个可能的字符串结果
第6行： 创建函数x，内部变量分别为字符串b，左括号数量i，右括号数量j
第7行： 若左右括号数量都等于n时，在列表a中加入当前字符串的副本
第8行： 若左括号数量小于右括号数量（比如())）时，不符合括号结合规律，结束本次函数
第9-10行： 当左括号数量小于等于n时，给字符串b加上左括号并进行下次函数
第11-12行： 当右括号数量小于等于n时，给字符串b加上右括号并进行下次函数
第13-14行： 使用函数x并返回最后得到的列表a
代码运行结果为：
更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。
想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。
- 发表于 2022-04-06 16:29
- 阅读 ( 604 )
- 分类：Python开发
