有效的括号
WangScaler: 一个用心创作的作者。声明：才疏学浅，如有错误，恳请指正。
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
分析
初步思考
这个题上大学的时候，就做过无数次，和水仙花数等等一样，印象深刻。
初步思路就是hashMap存储（、{、[。起初值为0。当遇到（、{、[时加1。遇到')'，'}'，']' 则判断hashMap对应的值是否大于0。如果不大于0则认为无效。如果大于0,则将hashMap的值进行减1。直到最后hashMap的值都是0,则认为有效。看似是没问题，但是有bug。例如{(}{)}这种明显不符合要求，但是却符合我们的刚才的解题算法。
继续思考
要解决上述的bug，必须要把先后顺序标记出来。可以看出来，我们左半边符号后进的，那么必须右半边符号先出。这很显然和我们栈的特性是一模一样的，后进先出。也就是说，我们遇到（、{、[时，就把将当前值压入栈中。遇到')'，'}'，']' 就从栈顶取出元素，而HashMap中存储的就是后半部分和前半部分的映射关系。如果取出的元素和hashMap的值对比不一致的话就认为无效，如果遍历结束，则认为是个合法的字符串。
答案
public static boolean isValid(String s) {
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack();
Map<Character, Character> hashMap = new HashMap<Character, Character>();
hashMap.put('}', '{');
hashMap.put(']', '[');
hashMap.put(')', '(');
for (int i = 0; i < s.length(); i++) {
if (hashMap.containsKey(s.charAt(i))) {
if (stack.isEmpty())
return false;
if (stack.pop() != hashMap.get(s.charAt(i))) {
return false;
}
}
stack.push(s.charAt(i));
}
return stack.isEmpty();
}这里如果我们字符串的长度如果不是偶数，那么肯定有一个符号，没法配对，此种情况肯定不是合法的字符串。
复杂度
- 时间复杂度：O(n)。其中n就是我们字符串的长度。
- 空间复杂度：O(n +∣Σ∣)。其中n就是我们栈中元素的个数，为字符串的一半，∣Σ∣就是hashMap的大小，此处只有六个字符串，所以就是6。
总结
简单题型的题确实不是很难，这个题只要看出是栈，那么问题就变得很简单了。如果看不出是栈，顺着初步思路去解决那个bug的话，至少得有一个标记位来标记最新的左半边符号。hashMap是个好东西，我们在很多算法题都用到了这个，在此建议不熟悉hashMap底层原理的朋友去学习学习。
都来了，点个赞再走呗！关注WangScaler，祝你升职、加薪、不提桶！
