【Amazon面经】Generate Parentheses Amazon 奇怪的一轮 开发岗

胖蛋 2020-6-5 1189


Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[  

   "((()))",

   "(()())",

   "(())()",

   "()(())",

   "()()()"

]

最新回复 (1)
  • Crusader 2021-3-2
    0 引用 2
    
    
    #!/usr/bin/python
    #-*- coding:utf-8 -*-
    
    """
       由于这题和检查有效括号字符串那题属于一个上下文,一些面试者会想到一个清奇的思路,就是先生成
       全部的排列然后再排除无效的。这种思路就不赘述了,肯定会被判定为不优的。
    
       正确的思路应该就是递归(recursion)。简单思路就是如果有n对括号,那么每个字符串就一定有2n个字符,
       每生成一个字符实际上都在做一个二分决策,即“我是接下来生成开阔号'('好呢,还是闭括号')'好呢?“
       如果决策正确,我们将最终得到一个有效的括号字符串,便可将其加入solution_set当中去。
    
       从二叉树的角度可以可视化这个过程(n=2为例):
                           ''
                           / 
                        '('     
                       /    \    
                     '()'   '(('
                     /         \
                   '()('       '(()'
                   /             \
               '()()'           '(())'
    
       虽然我们最终只取二叉树的叶子节点,但是实际上我们还是遍历了途径节点,所以算法时间复杂度是O(2^n)。
    
       如果被要求写循环(iteration)的方式做的话,借助一个有Stack(栈)功能的数据结构就能搞定了。
    
       任何recursion能解决的问题都是借助了函数本身call stack的特性,都可以想到在转循环写法的时候用到栈。
    """
    
    def generate_parentheses(n):
       solution_set = []
       # 基础参数:空结果集,空字符串,已添加0个开括号,已添加0个闭括号,需要填充n对括号
       generate_parentheses_recursive(solution_set, "", 0, 0, n)
       return solution_set
    
    def generate_parentheses_recursive(solution_set, current, num_open, num_close, n):
       # 当已添加开括号和已添加闭括号都达到n时:
       if (num_open == n and num_close == n):
           # 得到了一个有效的括号字符串,将其加入结果集
           solution_set.append(current)
       # 当开括号还不够时:
       if num_open < n:
           # 继续添加开括号
           generate_parentheses_recursive(solution_set, current+"(", num_open+1, num_close, n)
       # 当开括号已满,但闭括号还不够时:
       if num_open > num_close:
           #继续添加闭括号
           generate_parentheses_recursive(solution_set, current+")", num_open, num_close+1, n)
    
    def generate_parentheses_iterative(n):
       solution_set = []
       s = []
       s.append(("", 0, 0, n))
       while (len(s) != 0):
           top = s.pop()
           if (top[1] == n and top[2] == n):
               solution_set.append(top[0])
           if top[1] < n:
               s.append((top[0]+"(", top[1]+1, top[2], n))
           if top[1] > top[2]:
               s.append((top[0]+")", top[1], top[2]+1, n))
       return solution_set
    
    if __name__ == "__main__":
       print(generate_parentheses(3))
       print(generate_parentheses_iterative(3))```
    上传的附件:
返回