3

生成括号
给定 n 对括号，编写一个函数来生成格式正确的括号的所有组合。

例如，给定 n = 3，解集为：

“((()))”、“(()())”、“(())()”、“()(())”、“()()()”

就个人而言，我认为
 时间复杂度
= O(n!)（不包括复制 tmpStr 的时间），n 是输入，
= O(n * n!)（包括复制 tmpStr 的时间）。

空间复杂度
= O(n)（堆栈空间使用），
= O(n)（堆栈 + 递归空间使用）。
代码：Java

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();

        // Input checking.
        if (n <= 0) {
            list.add("");
            return list;
        }

        String tmpStr = "";
        for (int i = 0; i < n; i ++) tmpStr += "(";

        helper(n, tmpStr, 0, list);

        return list;
    }

    private void helper(int n, String tmpStr, int start, List<String> list) {
        // Base case.
        if (tmpStr.length() == 2 * n) {
            if (isValid(tmpStr)) list.add(tmpStr);
            return;
        }

        for (int i = start; i < tmpStr.length(); i ++) {
            // Have a try.
            tmpStr = tmpStr.substring(0, i + 1) + ")" + 
                     tmpStr.substring(i + 1, tmpStr.length());

            // Do recursion.
            helper(n, tmpStr, i + 1, list);

            // Roll back.
            tmpStr = tmpStr.substring(0, i + 1) + 
                     tmpStr.substring(i + 2, tmpStr.length());
        }
    }

    private boolean isValid(String str) {
        // Input checking.
        if (str == null || str.length() < 2) return false;

        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < str.length(); i ++) {
            char curr = str.charAt(i);
            if (curr == '(') stack.push(curr);
            else {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }

        if (stack.isEmpty()) return true;
        else return false;
    }
}
4

1 回答 1

2

如果您可以对验证方法进行一些更改，则可以为较大的n. 您可以使用计数器而不是堆栈来检查验证。像这样的东西

 private boolean isValid(String str)
  {
    // Input checking.
    if (str == null || str.length() < 2)
    {
      return false;
    }
    int ct = 0;
    for (int i = 0; i < str.length(); i++)
    {
      char curr = str.charAt(i);
      if (ct < 0)
      {
        return false;
      }
      if (curr == '(')
      {
        ct++;
      }
      else if (curr == ')')
      {
        ct--;
      }
    }
    if (ct != 0 || ct < 0)
    {
      return false;
    }
    else
    {
      return true;
    }
  }

我在我的机器上运行它，节省的时间n=13大约是2 sec，使用这种方法，算法的总执行时间小于2 sec. 为了n=15节省时间12 sec。

这不仅可以节省时间，还可以节省大量内存。

于 2014-08-12T05:58:51.453 回答