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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题目要求传入任意一个数字n,输出n对括号的任意组合,以List<String>类型返回

先画个草图了解一下

1:左右括号都有n个,List<String>里每个元素长度都是n*2

2:当字符串长度达到了n*2,可以添加到List<String>里

3:左括号可以随意添加,没限制

4:右括号只能在当前右括号数量比左括号数量小的时候添加,否则新来的右括号就没法匹配了;

这基本就理除了递归实现的逻辑,2为结束条件,3,4为递归条件

Java源码如下

package com.maoxiaomeng;

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

/**
* Copyright (C), 2014-2018, maoxiaomeng.com
* FileName: Solution
* Author: lihui
* Date: 2018/4/14 00:37
*/

public class Solution {
public List<String> generateParenthesis(int n) {
List<String> myList = new ArrayList<String>();
if (n < 1) {
return myList;
}

String currentStr = "";
recursionParenthesis(myList, currentStr, 0, 0, n);
return myList;
}

public void recursionParenthesis(List<String> list, String currentStr,
int left, int right, int n) {
if (currentStr.length() == n * 2) {
list.add(currentStr);
return;
}

if (left < n) {
recursionParenthesis(list, currentStr + "(", left + 1, right, n);
}

if (left > right) {
recursionParenthesis(list, currentStr + ")", left, right + 1, n);
}
}
}

这种正向递归的方法,参考了LeetCode里C++实现的一种Solution,一般人的解法是反向递归(这两天,看着递归就头大……)

1:以剩下未传入的括号为基准

2:当剩下的左右括号都没了,结束

3:左括号随便加,剩下的左括号就随便减少

4:当剩下的左括号比右括号少,也就是左括号用出去的更多,可以加右括号,同时剩下的右括号减少

基本条件都和上面递归正好互补的

package com.maoxiaomeng;

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

/**
* Copyright (C), 2014-2018, maoxiaomeng.com
* FileName: Solution
* Author: lihui
* Date: 2018/4/14 00:37
*/

public class Solution {
public List<String> generateParenthesis(int n) {
List<String> myList = new ArrayList<String>();
if (n < 1) {
return myList;
}

String currentStr = "";
recursionParenthesis(myList, currentStr, n, n);
return myList;
}

public void recursionParenthesis(List<String> list, String currentStr,
int left, int right) {
if (left == 0 && right == 0) {
list.add(currentStr);
return;
}

if (left > 0) {
recursionParenthesis(list, currentStr + "(", left - 1, right);
}

if (left < right) {
recursionParenthesis(list, currentStr + ")", left, right - 1);
}
}
}

反正思路都一样,就是递归条件一朵,大脑不够用了

发表回复