要求生成所有“合法”的括号字符串,就首先需要弄清楚括号字符串的合法性定义,也就是说如果我们现在有一个由小括号组成的字符串,该如何判断其是否符合要求。此前做过判断括号串是否合法的题目,那道题目中一般在遍历过程中维护一个栈,因为每个后括号都需要在已经遍历的子串中找到自己对应的前括号。这个题目中的合法性判断应该稍微简单一些,因为本题中只有小括号一种括号,因此我们可以将使用栈存储前面遍历的元素,简化为使用一个整型变量维护前括号的数量。这样一来,实际实现过程可以使用open
存储前括号的数量,close
存储后括号的数量,遍历结束时只有open == close
时字符串才合法,此外,整个遍历过程中open >= close
都需要成立,毕竟后括号必须有且仅有一个对应的前括号。
bool check(string& s, int n) {
int open = 0, close = 0;
for (char c : s) {
switch (c) {
case '(':
open++; break;
case ')':
close++; break;
default:
return false;
}
if (open > n) return false;
if (close > open) return false;
}
return true;
}
只关心open
和close
的大小关系,就可以将两个变量简化为一个变量balance
,可以理解成前后括号的数量是否平衡。
bool check(string& temp) {
int balance = 0;
for (const char& c : temp) {
if (c == '(') balance++;
else balance--;
if (balance < 0) return false;
}
if (balance == 0) return true;
else return false;
}
明确了如何判断括号字符串的合法性,就可以想用回溯算法枚举所有可能的括号字符串,将所有合法的结果存入结果数组中返回。
void backtrack(vector<string>& result, string& s, int idx, int n) {
if (idx >= 2 * n) {
if (check(s, n)) result.push_back(s);
return;
}
s.push_back('(');
backtrack(result, s, idx + 1, n);
s.pop_back();
s.push_back(')');
backtrack(result, s, idx + 1, n);
s.pop_back();
}
vector<string> generateParenthesis(int n) {
vector<string> result;
string s;
backtrack(result, s, 0, n);
return result;
}
但是其实没有必要将整个串枚举完,而是可以在枚举过程中判断当前子串的合法性,即前括号与后括号的数量关系,因为显然如果前面一部分子串已经不合法,再继续深入下去的整个串一定不可能合法。这实际上也是一种对回溯算法的剪枝。
class Solution {
public:
void backtrack(vector<string>& res, string& temp, int open, int close, int n) {
if (temp.length() == n * 2) {
res.push_back(temp);
return;
}
if (open < n) {
temp.push_back('(');
backtrack(res, temp, open + 1, close, n);
temp.pop_back();
}
if (close < open) {
temp.push_back(')');
backtrack(res, temp, open, close + 1, n);
temp.pop_back();
}
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string temp;
backtrack(res, temp, 0, 0, n);
return res;
}
};
顺带一提,这个题目需要对字符串进行回溯,C++中的字符串实际上就是一个字符向量数组,但是Java中需要使用StringBuilder
或者StringBuffer
提供的接口。根据力扣的提测结果,前者更快些(但是缺点在于线程不安全)。