原题链接：Leetcode 20. Valid Parentheses
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.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]" Output: false
Constraints:
- 1 <= s.length <= 104
- s consists of parentheses only ‘()[]{}’.
方法一：栈 思路：
栈的应用之括号匹配模板题
c++代码：class Solution {
public:
bool isValid(string s) {
stack st;
// 遍历整个字符串
for(auto c : s){
// 左括号就入栈
if(c == '(' || c == '[' || c == '{'){
st.push(c);
}
else{
if(st.empty()){
return false;
}
if(st.top() == '(' && c == ')') st.pop();
else if(st.top() == '[' && c == ']') st.pop();
else if(st.top() == '{' && c == '}') st.pop();
else
return false;
}
}
if(!st.empty())
return false;
return true;
}
};
复杂度分析：
- 时间复杂度：O(n)，字符串的长度
- 空间复杂度：O(n)
