leetcode: Generate Parentheses

问题描述

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

 

原问题链接：https://leetcode.com/problems/generate-parentheses/

 

问题分析

   这个问题有几种解决方法，我们逐一讨论。

 

方法一：

     我们首先从最简单的情况看过来，当只有一对括号的时候，肯定结果就是最简单的"()"。而如果有两对括号的时候，我们会怎么考虑呢？我们会考虑把新的括号加到原来的某个地方，让它们构成一个新的串，所以如果我们在原来的字符串前加上一组括号，则构成这么一个串："()()"，如果在第一个元素后加上一组括号，则构成串"(())"，在最后一个元素后面加上这个串，则构成串"()()"。当然，这里最后的元素拼接成的串和最前面的元素拼接成的串是一样的。我们需要去除这些重复的串。

    按照这里的讨论，可以得到这样的一种思路。首先根据字符串"()"，在它的每个元素相间的地方加入一对括号，这样构成了3个串。将这些形成的串加到一个set中来消除重复的串。这样就从一组括号扩展到了两组括号组合的情况。再这样依次类推到n组括号的情况。具体的实现代码如下：

 

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if(n < 1) return result;
        result.add("()");
        for(int i = 1; i < n; i++) {
            Set<String> set = new HashSet<>();
            for(String s : result) {
                for(int j = 0; j < s.length(); j++) {
                    set.add(s.substring(0, j) + "()" + s.substring(j, s.length()));
                }
            }
            List<String> temp = new ArrayList<>(set.size());
            temp.addAll(set);
            result = temp;
        }
        
        return result;
    }
}

    上述方法的实现效率并不是很高，其时间复杂度达到了O(N^3)。 

 

方法二

    前面第一个办法的效率不太高的原因是一方面它要针对里面所有前面元素的位置去加括号，而实际上里面有很多是重复的。这样浪费了不少时间。而且里面各种字符串的拼接也是比较影响效率的。那么还有没有别的办法呢？

    我们可以换一种思路来看这个问题。这个问题无非就是给定了n组括号，也就是说有n个左括号，n个右括号。那么，我们就是需要组合出来所有合法的括号组。作为一个合法的括号组合，它应该符合一个什么条件呢？实际上它应该确保这个串的从头开始的任何一个子串都必须是左括号数量不小于右括号数量。这样我们可以定义一个递归的函数，perm(int open, int close, char[] perm, int i)。其中open表示左括号的数量，close表示右括号的数量，而i表示我们要构造的字符串当前正在递归构造的位置。这个递归函数的退出条件是i == perm.length。而perm则是我们用来填充括号来构造的最终的串。它的长度是2 * n。

   在递归的过程中要保证open <= close。而且递归条件退出的时候需要将结果添加到最终的List中。

    最终的代码实现如下：

 

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] perm = new char[n * 2];
        perms(n, n, perm, 0, res);
        return res;
    }
    
    private void perms(int open, int close, char[] perm, int i, List<String> res) {
        if (i == perm.length) {
            res.add(new String(perm));
            return;
        }
        if (open > 0 && close >= open) {
            perm[i] = '(';
            perms(open - 1, close, perm, i + 1, res);
        }
        if (close > 0) {
            perm[i] = ')';
            perms(open, close - 1, perm, i + 1, res);
        }
    }
}

    这种递归的实现有一个好处，就是它不用做大量的字符串拼接和去重操作。效率上要高一些。当然，要能够得出上述的这种递归表达式还是需要一番推敲的。这种方法值得深入分析。

 

总结

    生成所有n组括号的问题可以概括成一个递归的问题。用这种方式的实现比较精炼也很巧妙。值得详细品味。

 

 

评论

2 楼 shihengli2010 2017-06-12  

跟着你的博客学习leetcode

1 楼 shihengli2010 2017-06-12