LeetCode 22. 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: [ "((()))", "(()())", "(())()", "()(())", "()()()"] Subscribe to see which companies asked this question.

题目

给定 n 对括号,请写一个函数以将其生成新的括号组合,并返回所有组合结果。 样例 给定 n = 3, 可生成的组合如下: "((()))", "(()())", "(())()", "()(())", "()()()"

分析

针对一个长度为2n的合法排列,第1到2n个位置都满足如下规则:左括号的个数大于等于右括号的个数。所以,我们就可以按照这个规则去打印括号:假设在位置k我们还剩余left个左括号和right个右括号,如果left>0,则我们可以直接打印左括号,而不违背规则。能否打印右括号,我们还必须验证left和right的值是否满足规则,如果left>=right,则我们不能打印右括号,因为打印会违背合法排列的规则,否则可以打印右括号。如果left和right均为零,则说明我们已经完成一个合法排列,可以将其打印出来。通过深搜,我们可以很快地解决问题,针对n=2,问题的解空间如下

Paste_Image.png

代码

public class Solution {
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
     public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<String>();
        if (n <= 0) {
            return result;
        }
        helper(result, "", n, n);
        return result;
    }
    
    public void helper(ArrayList<String> result,
                       String paren, // current paren
                       int left,     // how many left paren we need to add
                       int right) {  // how many right paren we need to add
        if (left == 0 && right == 0) {
            result.add(paren);
            return;
        }

        if (left > 0) {
            helper(result, paren + "(", left - 1, right);
        }
        
        if (right > 0 && left < right) {
            helper(result, paren + ")", left, right - 1);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 最长上升子序列题目分析

给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。 说明最长上升子序列的定义: 最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的...

7320
来自专栏陈树义

1.Java集合总结系列:Java集合概述

一、概述 集合是 Java 中非常重要的 API,在实际应用中非常广泛,在许多面试中也是必考的知识点。 Java 所有集合类都位于 java.util 包下,J...

40080
来自专栏郭耀华‘s Blog

Java容器类List、ArrayList、Vector及map、HashTable、HashMap的区别与用法

Java容器类List、ArrayList、Vector及map、HashTable、HashMap的区别与用法 ArrayList 和Vector是采用...

41680
来自专栏向治洪

java基础之泛型

泛型 术语 "?"通配符 通配符的扩展 自定义泛型方法 "擦除"实例 类型参数的类型推断 自定义泛型类 泛型方法和泛型类的比较 泛型和反射 通过反射获...

32060
来自专栏偏前端工程师的驿站

Java魔法堂:解读基于Type Erasure的泛型

一、前言                               还记得JDK1.4时遍历列表的辛酸吗?我可是记忆犹新啊,那时因项目需求我从C#转身到Jav...

22850
来自专栏Albert陈凯

2018-09-21 JAVA的集合类关系总结,基础知识太不扎实了

*面向对象语言对事物的体现都是以对象的形式,所以为了方便对多个对象的操作,就对对象进行存储,集合就是存储对象最常用的一种方式。

9430
来自专栏石奈子的Java之路

原 java数据结构与算法之数组篇

21440
来自专栏吾爱乐享

java之学习泛型的概述和基本使用

16560
来自专栏mathor

JDK1.5泛型

13840
来自专栏陈树义

6.Java集合总结系列:常见集合类的使用(List/Set/Map)

MARK 总结: Set、List 和 Map 可以看做集合的三大类。 List集合是有序集合,集合中的元素可以重复,访问集合中的元素可以根据元素的索引来访问。...

36350

扫码关注云+社区

领取腾讯云代金券