[Day11]22. Generate Parentheses

Late again.
MEDIUM level again. But this one is interesting.

DESCRIPTION:
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

ANALYSIS:
One thing we know about this problem is to lengthen it one by one. If you are a seasonal player, maybe you would find that 'Oh! Recursion!'. But I am not one of those ones. So, I ask SLF again, and he told me to use 'classified discussion' and 'recursion'.

SOLUTION:

According to the hint given by SLF, code by myself, around 1 hour:

package leetcode;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class p22_Generate_Parentheses {

    static List<String> results = new ArrayList<String>();
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            List<String> results = new ArrayList<String>();
            results = generateParenthesis(n);
            for (int i = 0; i < results.size(); i++) {
                System.out.println(results.get(i));
            }
            System.out.println("--------------");
        }
    }

    public static List<String> generateParenthesis(int n) {
        String s = "";
        addOne(s, n);
        return results;
    }

    private static void addOne(String s, int n) {
        if (s.length() < n * 2) {
            int[] lr = countlr(s);
            int l = lr[0];
            int r = lr[1];
            if (l == r) {
                addOne(s + '(', n);
            } else if (l == n) {
                addOne(s + ')', n);
            } else if (l > r) {
                addOne(s + '(', n);
                addOne(s + ')', n);
            }
        } else {
            results.add(s);
        }
    }

    private static int[] countlr(String string) {
        int countl = 0;
        int countr = 0;
        for (int i = 0; i < string.length(); i++) {
            if (string.charAt(i) == '(')
                countl++;
            else
                countr++;
        }
        int[] result = { countl, countr };
        return result;
    }
}

And this is the top solution on SLF'S JianShu, whose idea enlighten me.

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }


    public void backtrack(List<String> list, String str, int open, int close, int max){
        //若长度达到 max*2 说明完整了,加入到 list 里面
        if(str.length() == max*2){
            list.add(str);
            return;
        }
        //当 open<max 时可以添加 (,并 open+1
        if(open < max)
            backtrack(list, str+"(", open+1, close, max);
        //当 close < open 时可以添加 ),并 close+1
        if(close < open)
            backtrack(list, str+")", open, close+1, max);
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容