LeetCode 22. Generate Parentheses 生成括号 Python 回溯解法
LeetCode 22. Generate Parentheses 生成括号 Python 回溯解法
大鹅
发布于 2021-06-15 15:30:36
发布于 2021-06-15 15:30:36
题目描述
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. 给定n对括号，写一个函数来生成成对的括号的所有组合。
For example, given n = 3, a solution set is: [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
解法#1
如果左括号还有剩余，则可以放置左括号，如果右括号的剩余数大于左括号，则可以放置右括号。
class Solution:
# @param an integer
# @return a list of string
def generateParenthesis(self, n):
res = []
self.generate(n, n, "", res)
return res
def generate(self, left, right, str, res):
if left == 0 and right == 0:
res.append(str)
return
if left > 0:
self.generate(left - 1, right, str + '(', res)
if right > left:
self.generate(left, right - 1, str + ')', res) 解法#2
回溯中每次遍历字符串s寻找右括号，若右括号在位置i，在此之前的字符串左括号数大于右括号数，且前一个字符为左括号，则与前一字符交换。
class Solution(object):
result_list = []
def generateParenthesis(self, n):
global result_list
def generate(s):
global result_list
new_s = s
left = right = 0
for i in range(n * 2):
if s[i] == '(':
left += 1
else:
right += 1
if left > right and s[i - 1] == '(':
new_s = s[:i - 1] + s[i:i + 1] + s[i - 1:i] + s[i + 1:]
if new_s not in result_list:
result_list += [new_s]
generate(new_s)
s = '(' * n + ')' * n
result_list = [s]
generate(s)
return result_list本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-01-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录