Given a string s
containing just the characters '(
', ')
', '{
', '}
', '[
' and ']
', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Solution
点击查看代码
class Solution {
private:
stack<char> sk1;
public:
bool isValid(string s) {
int n = s.size();
if(n%2)return false;
for(int i=0;i<n;i++){
if(s[i]=='(' || s[i]=='[' || s[i]=='{')sk1.push(s[i]);
else{
if(!sk1.empty()){
auto f = sk1.top(); sk1.pop();
if(f=='('){
if(s[i]==')')continue;
else return false;
}
else if(f=='['){
if(s[i]==']')continue;
else return false;
}
else if(f=='{'){
if(s[i]=='}')continue;
else return false;
}
}
else return false;
}
}
if(!sk1.empty())return false;
return true;
}
};