LeetCode：20. 有效的括号

简介题目链接https://leetcode.cn/problems/valid-parentheses/description/解决方式字符串 栈 / 栈、映射栈实现思路迭代字符遇到左括号则放入栈中否则根据当前的右括号去栈中匹配。栈顶元素若不是右括号对应的左括号就证明包含无效括号。迭代结束后栈中应无数据有则证明左括号多了。classSolution{publicbooleanisValid(Strings){intns.length();// 转换为字符数组char[]chs.toCharArray();// 栈StackCharacterstacknewStack();// 循环for(inti0;in;i){// 左括号加入栈if(ch[i](||ch[i]{||ch[i][){stack.add(ch[i]);}else{// 右括号匹配if(stack.isEmpty()){returnfalse;}if(ch[i])stack.pop()!(){returnfalse;}elseif(ch[i]}stack.pop()!{){returnfalse;}elseif(ch[i]]stack.pop()![){returnfalse;}}}// 循环结束栈中应无数据若有则有无效括号returnstack.size()0?false:true;}}栈、映射实现思路这是另一种写法将左右括号的匹配加入映射而非直接硬编码。这种写法时间复杂度较高。classSolution{publicbooleanisValid(Strings){// 边界处理if(s||s.length()%2!0){returnfalse;}// 有效括号映射MapCharacter,CharacterpairsnewHashMap();pairs.put(),();pairs.put(],[);pairs.put(},{);// 栈DequeCharacterstacknewArrayDeque();// 循环遇到左括号入栈遇到右括号则匹配栈中的左括号for(inti0;is.length();i){charcs.charAt(i);if(pairs.containsKey(c)){// 栈为空 或 栈顶不匹配 - 无效if(stack.isEmpty()||stack.pop()!pairs.get(c)){returnfalse;}}else{// 左括号直接入栈stack.push(c);}}// 所有字符处理完后栈应为空。不为空则有无效括号。returnstack.isEmpty();}}