给定一个仅包含 '('、')'、'{'、'}'、'['、']'的字符串，确定输入的字符串是否合法。
e.g. "()"、"()[]{}"、"[()]([]({}))" 是合法的，而"(]"、"([)]" 是不合法的。
使用栈stack
C++实现：
bool isValid(string s) {
stack<char> stack;
for (char &c : s) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.empty() || (stack.top() != c))
return false;
else
stack.pop();
}
return stack.empty();
}
对应的Java实现：
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
C++中的stack，其中有两个方法：
- pop()，返回void，不返回类型<T>。
- top()，返回栈顶的引用。
pop()不返回栈顶元素的原因是：
- 异常安全原因
如果要实现，代码如下，
template<class T>
T stack<T>::pop() {
if( vused_ == ) {
throw "pop from empty stack";
} else {
return v_[--vused_ - ];
}
}
试图返回 v_[--vused_ - 1] 的时候，会调用 T 的拷贝构造函数，如果调用的时候发生异常，并没有返回正确的值，但是栈顶元素已经弹出了，这时就丢失了栈顶数据。
如果这样写，
template<class T>
T stack<T>::pop() {
if( vused_ == ) {
throw "pop from empty stack";
} else {
T result = v_[vused_ - ];
--vused_;
return result;
}
}
先建立一个栈顶元素的副本，如果拷贝构造函数出现异常，那么 --vused_ 不会执行，就不会丢失数据。但假如 --vused_ 和 return result 之间发生异常，依然会出问题。也就是说，如果想同时做 pop() 和 top() ，一定要保证 --vused_ 和 return result 是一个执行事务。
- 效率原因
因为栈顶元素在栈中已经不存在，必须在按引用返回之前现将其存储到某个地方。如果选用动态内存，除非动态内存最终被删除，否则将导致内存泄露。
如果调用拷贝构造函数，对象按值传递的方式从函数返回，效率低下。
扩展 生成括号
给定 n 对括号，写出所有可能的合法括号组合。
e.g. 给定 n = 3，结果集为
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
我的思路是递归
vector<string> generateParenthesis(int n) {
if (n == ) {
return {"()"};
} else {
vector<string> result;
vector<string> pre = generateParenthesis(n - );
for (int i = ; i < pre.size(); i++) {
result.push_back("(" + pre[i] + ")");
result.push_back(pre[i] + "()");
if ("()" + pre[i] != pre[i] + "()")
result.push_back("()" + pre[i]);
}
return result;
}
}
算法没什么问题，可以生成所有可能的括号集合，但 vector 中存储的顺序不论怎么改都和答案的不一样。
答案使用的思路是DFS。创建一个函数来增加括号，str 表示加入到结果 vector<string> res 中的一项。
left 表示剩下的需要增加的“ ( ”的个数，初始为 n；right 表示当前的 str 中需要与没有配对的 “ ( ” 配对的 “ ) ” 的个数。
若 left > 0，则在 str 里加入一个“ ( ”，并让下次需要增加的“ ( ”的个数减 1，且因为加入了一个“ ( ”，该左括号没有右括号与之配对，所以当前 str 需要的“ ) ”加 1；
若 right > 0，说明需要在 str 里加入一个“ ) ”，下次需要的“ ) ”少 1 个就行了。
vector<string> generateParenthesis(int n) {
vector<string> result;
addParen(result, "", n, );
return result;
}
void addParen(vector<string> &res, string str, int left, int right) {
if (left == && right == ) {
res.push_back(str);
return;
}
if (left > )
addParen(res, str + "(", left - , right + );
if (right > )
addParen(res, str + ")", left, right - );
}
类似的，
这种方法个人觉得比上面的直观，一项 str 需要 n 个左括号和 n 个右括号，那么 left 和 right 都直接表示 str 所需要的“ ( ”和“ ) ”的个数。
注意的是，str 中一定要有没有配对的 “ （ ” 存在，才能加入 “ ) ”，所以加入右括号的判断条件是 if (right > left)。
vector<string> generateParenthesis(int n) {
vector<string> result;
addParen(result, "", n, n);
return result;
}
void addParen(vector<string> &res, string str, int left, int right) {
if (left == && right == ) {
res.push_back(str);
return;
}
if (left > )
addParen(res, str + "(", left - , right);
if (right > left)
addParen(res, str + ")", left, right - );
}
将 str 使用引用传参的话则不需要建立许多局部临时变量 str，可以节省一定的空间。
vector<string> generateParenthesis(int n) {
vector<string> result;
string str = "";
addParen(result, str, n, n);
return result;
}
void addParen(vector<string> &res, string &str, int left, int right) {
if (left == && right == ) {
res.push_back(str);
return;
}
if (left > ) {
str += "(";
addParen(res, str, left - , right);
str.resize(str.length() - );
}
if (right > left) {
str += ")";
addParen(res, str, left, right - );
str.resize(str.length() - );
}
}
注意 16 和 21 行 str.resize(str.length() - 1); 语句调用，由于 str 是引用，如果不重新设置 str 长度，str 会越来越长。
使用 pop_back 也可以
if (left > ) {
str.push_back('(');
addParen(res, str, left - , right);
str.pop_back();
}
if (right > left) {
str.push_back(')');
addParen(res, str, left, right - );
str.pop_back();
}