leetcode20题解
题目描述
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.
解题思路
针对左右括号的大模拟，我采用模拟堆栈的方式万测过
代码实现
class Solution {
public:
bool isValid(const string& s) {
vector<short> mystack;
mystack.reserve(s.size());
for(const auto &c:s){
switch(c){
case '(':
mystack.push_back(0);
break;
case ')':
if (mystack.empty()) return false;
else if(mystack.back()==0) mystack.pop_back();
else return false;
break;
case '{':
mystack.push_back(1);
break;
case '}':
if (mystack.empty()) return false;
else if(mystack.back()==1) mystack.pop_back();
else return false;
break;
case '[':
mystack.push_back(2);
break;
case ']':
if (mystack.empty()) return false;
else if(mystack.back()==2) mystack.pop_back();
else return false;
break;
default:
return false;
}
}
if(!mystack.empty()) return false;
return true;
}
};