题目描述
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
假设我们有一串(,),[,],{,}的字符串s。我们要判断这串字符串是不是一串有效的组合。比如[]{()}是遗传有效的组合。[)[]}是一串无效的组合。
代码及其注释
class Solution {
public:
bool isValid(string s) {
string left = "([{";
string right = ")]}";
stack<char> stk;
for(auto c : s){
if(left.find(c) != string::npos){
stk.push(c);
}
else{
if(stk.empty() || stk.top() != left[right.find(c)]){
return false;
}
else{
stk.pop();
}
}
}
return stk.empty();
}
};
分析
用一个stack就可以了，把s里面的字符一个一个过一遍。
1 如果我们遇到 ([{ 里面的一个，就把这个字符放入stack里面。
2 如果我们遇到 )]} 里面的一个，就把这个字符和stack最顶端的字符进行比较：
(a)如果遇到的字符和stack顶端字符相等，把stack顶端的字符去掉，然后继续比较字符串的下一个
(b)如果遇到的字符和stack顶端的不相等，就返回false。
当把s里面的字符串都过了一遍以后，再看stack是不是空，如果空就返回true。不空就返回false。
