[LeetCode] 22. Generate Parentheses_Medium tag: backtracking
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode] 22. Generate Parentheses_Medium tag: backtracking，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1483字，纯文字阅读大概需要3分钟。
内容图文
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1 Output: ["()"]
Constraints:
-
1 <= n <= 8
Idea:
backtracking.
Code1, generate all pairs with 2 * n, then check whether they are valid parentheses.
T: O(2^(2n) * n)
S: O(2^(2n) * n)
class
Solution:
def
generateParentheses(self, n):
ans = []
def helper(ans, temp, n):
if len(temp) == 2 * n and self.isValid(temp):
ans.append(temp)
elif len(temp) < 2 * n:
helper(ans, temp + ‘(‘, n)
helper(ans, temp + ‘)‘, n)
helper(ans, "", n)
def isValid(self, s):
count = 0
for c in s:
if c == ‘(‘:
count += 1
else:
count -= 1
if count < 0:
return False
return count == 0
Idea 2, we know that with 2 * n length parentheses, we need to have n ‘(‘ and n ‘)‘, so in the helper function, add left and right to count the number of ‘(‘ and ‘)‘.
Time: O(2^(2n) * n /n/ n ^ (1/2)) = 4^n/n ^ (1/2)
Space : O(2^(2n) * n /n/ n ^ (1/2)) = 4^n/n ^ (1/2)
class
Solution:
def
generateParentheses(self, n):
ans = []
def helper(ans, temp, left, right, n):
if len(temp) == 2 * n:
ans.append(temp)
elif len(temp) < 2 * n:
if left < n:
helper(ans, temp + ‘(‘, left + 1, right, n)
if right < left:
helper(ans, temp + ‘)‘, left, right + 1, n)
helper(ans, "", 0, 0, n)
return ans
原文：https://www.cnblogs.com/Johnsonxiong/p/14860154.html
内容总结
以上是互联网集市为您收集整理的[LeetCode] 22. Generate Parentheses_Medium tag: backtracking全部内容，希望文章能够帮你解决[LeetCode] 22. Generate Parentheses_Medium tag: backtracking所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。