要一遍做对——LeetCode题目20：有效的括号
原题描述
+
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1
输入："()"
输出：true
示例 2
输入："()[]{}"
输出：true
示例 3
输入："(]"
输出：false
示例 4
输入："([)]"
输出：false
示例 5
输入："{[]}"
输出：true
原题链接：https://leetcode-cn.com/problems/valid-parentheses
思路解析
+
即便是面试官有意放水，这道题还是有人做不对，因为心思不够缜密。知道用栈来判断有效性，但是不合法的条件有几种，你能一下想全吗？
当前扫描到右括号时，和栈顶不匹配；
当前扫描到右括号时，栈空了；
字符串扫描结束了，但是栈没有清空。
这道题现实中考的可能性很小，但自己还是做一做吧，就当一次娱乐了~
复杂度分析
+
时间复杂度：
空间复杂度：
C++参考代码
+
class Solution {
public:
bool isValid(string s) {
map<char, char> table = {
{')', '('}, {']','['}, {'}','{'}
};
stack<char> my_stack;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
my_stack.push(s[i]);
} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (my_stack.size() == 0 || table[s[i]] != my_stack.top()) return false;
else my_stack.pop();
}
}
bool suc = my_stack.size() == 0 ? true: false;
return suc;
}
};讲技术，也谈风月，更关注程序员的生活状况，欢迎联系二少投稿你感兴趣的话题。