LeetCode 22. Generate Parentheses

題目來源：https://leetcode.com/problems/generate-parentheses/

問題描述

22. Generate Parentheses

Medium

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:

[

  "((()))",

  "(()())",

  "(())()",

  "()(())",

  "()()()"

]

------------------------------------------------------------

題意

給出整數n，求n對括号組成的所有合法括号序列

------------------------------------------------------------

思路

動态規劃。n對括号的序列可以由(n-1)對括号的所有空隙中插入一對括号得到，再用set去重即可。例如，要求n=3, 從n=2的結果[“()()”, “(())”]出發：

.()() -> ()()()

(.)() -> (())()

().() -> ()()()

()(.) -> ()(())

()(). -> ()()()

.(()) -> ()(())

(.()) -> (()())

((.)) -> ((()))

(().) -> (()())

(()). -> (())()

------------------------------------------------------------

代碼

class Solution {
    public List<String> generateParenthesis(int n) {
        if (n == 0)
        {
            return new LinkedList<String>(){
                {
                    add("");
                }
            };
        }
        Set<String> ret = new HashSet<String>() {
            {
                add("");
            }
        };
        int i = 0, j = 0, len = 0;
        for (i=1; i<=n; i++)
        {
            Set<String> pret = new HashSet<String>(ret);
            ret.clear();
            for (String str: pret)
            {
                len = str.length();
                for (j=0; j<len; j++)
                {
                    String nstr = str.substring(0, j) + "()" + str.substring(j);
                    ret.add(nstr);
                }
                ret.add(str + "()");
            }
        }
        return new LinkedList<String>(ret);
    }
}