LeetCode22括号生成
暴力解法
我们可以生成所有 2^{2n}个 '(' 和 ')' 字符构成的序列，然后我们检查每一个是否有效即可。
为了检查序列是否有效，我们遍历这个序列，并使用一个变量 balance 表示左括号的数量减去右括号的数量。
如果在遍历过程中 balance 的值小于零，或者结束时 balance 的值不为零，那么该序列就是无效的，否则它是有效的。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList<String>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current)) {
result.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
}
回溯法
对暴力解法的改进，不需要遍历所有可能，我们可以只在序列仍然保持有效时才添加 '(' or ')'
而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
if (cur.length() == max * 2) {
ans.add(cur.toString());
return;
}
if (open < max) {
cur.append('(');
backtrack(ans, cur, open + 1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) {
cur.append(')');
backtrack(ans, cur, open, close + 1, max);
cur.deleteCharAt(cur.length() - 1);
}
}
}
dfs
与方法二相似
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(n, n, "");
return res;
}
private void dfs(int left, int right, String curStr) {
if (left == 0 && right == 0) {
res.add(curStr);
return;
}
if (left > 0) {
dfs(left - 1, right, curStr + "(");
}
if (right > left) {
dfs(left, right - 1, curStr + ")");
}
}
动态规划
按照括号规则进行添加括号
规则就是任何一个括号都可以用
(a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。
函数generate(n)表示n个括号的表示情况，所以要想求第n个括号就要求第n-1个括号情况。而n-1也是这样求解。
注意：n==0特判
class Solution {
ArrayList[] cache = new ArrayList[100];
public List<String> generate(int n) {
if (cache[n] != null) {
return cache[n];
}
ArrayList<String> ans = new ArrayList<String>();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c) {
for (String left: generate(c)) {
for (String right: generate(n - 1 - c)) {
ans.add("(" + left + ")" + right);
}
}
}
}
cache[n] = ans;
return ans;
}
public List<String> generateParenthesis(int n) {
return generate(n);
}
}
Processed:
0.011, SQL:
8
