题目描述
Given a string 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.
Note that an empty string is also considered valid.
Input: “()”
Output: true
Input: “()[]{}”
Output: true
Input: “(]”
Output: false
解题思路
- 栈的简单应用
- 碰到左边部分，就入栈
- 碰到右边部分，检查栈元素是否为空，或者 top元素是否能够匹配
- 两个条件任意一个不成立就肯定不匹配
- 最后栈元素应该为空，否则就肯定不匹配
C++代码
class Solution {
public:
bool isValid(string s) {
stack<char> stack1;
for(int i = 0; i < s.size(); i++){
if(s[i] == '(' || s[i] == '{' || s[i] == '['){
stack1.push(s[i]);
}else if(s[i] == '}'){
if(stack1.empty() || stack1.top() != '{'){
return false;
}
stack1.pop();
}else if(s[i] == ')'){
if(stack1.empty() || stack1.top() != '('){
return false;
}
stack1.pop();
}else if(s[i] == ']'){
if(stack1.empty() || stack1.top() != '['){
return false;
}
stack1.pop();
}
}
if(stack1.empty()){
return true;
}else{
return false;
}
}
};
