LeetCode第[22]题(Java)：Generate Parentheses

题目：制造括号序列

难度：Medium

题目内容：

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:

[

  "((()))",

  "(()())",

  "(())()",

  "()(())",

  "()()()"

]

我的思路：这应该是典型的卡特兰数的应用的一种吧，对于这种输出所有**的可能组合，在一眼看不出来的情况下应该考虑卡特兰数，就是f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-1)f(0)，在这个题目上应该就是说，首先有n个括号，一共2n个符号，最左边的符号只能为"("并且与其搭配的右括号只能出现在 2i 的位置，所以此时第一个括号把整个序列分成两部分（2~2i-1）与后面的所有，这两个部分还能继续往下分，所以有此公式 : f(n) = ∑ f(i)f(n-1-i)

　　　　确定是卡特兰数之后，一般考虑使用递归法。

     public List<String> generateParenthesis(int n) {

         List<String> ans = new ArrayList();

         if (n == 0) {

             ans.add("");

         } else {

             for (int i = 0; i < n; i++)

                 for (String in: generateParenthesis(i))

                     for (String out: generateParenthesis(n-1-i))

                         ans.add("(" + in + ")" + out);

         }

         return ans;

     }

我的复杂度：时间：O（2n ! / (n!(n+1))）空间：O（2n ! / (n!(n+1))）递归次数就是计算次数，就是卡特兰数的计算公式。

编码过程中遇见问题：

1、在写遍历 in ，与 out 的时候，一开始是还写了个List<String> 来接函数结果，后来参考了下答案上面，才想着对于后面用不着的list可以直接使用foreach遍历

参考答案代码：

     public List<String> generateParenthesis(int n) {

         List<String> ans = new ArrayList();

         backtrack(ans, "", 0, 0, n);

         return ans;

     }

     public void backtrack(List<String> ans, String cur, int open, int close, int max){

         if (cur.length() == max * 2) {

             ans.add(cur);

             return;

         }

         if (open < max)

             backtrack(ans, cur+"(", open+1, close, max);

         if (close < open)

             backtrack(ans, cur+")", open, close+1, max);

     }

参考答案复杂度：时间：O（2n ! / (n!(n+1))）空间：O（2n ! / (n!(n+1))）

参考答案思路：使用了另外使用了一个方法，没有用卡特兰数的思想，而是使用了经典的递归思想“走一步看一步”，使不了解卡特兰数的人更容易看懂：

每要添加一个符号的时候都分两种情况。

　　　　a、如果已开的括号数“（”小于要打开的括号数，并且再打开一个括号“+（”，将已开括号数++，并调用下一层；

　　　　b、关闭括号数“)”小于已经打开括号数，则将关闭一个括号“+）”，将关闭数++，并调用下一层。

最后当str的长度为n的2倍时，把它加入结果集并返回。

这样一来每一种情况也能全部考虑到。

巴特西

LeetCode第[22]题(Java)：Generate Parentheses

最新文章

热门文章