图解算法——括号匹配 1. 题目描述 给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 2.示例 示例1： 输入：s = “()” 输出：true 示例2： 输入：s = “()[]{}” 输出：true 示例3： 输入：s = “(]” 输出：false 示例4： 输入：s = “([)]” 输出：false 示例5： 输入：s = “{[]}” 输出：true 3..提示： 仅由括号 组成 4. 解题思路： 由提示可知， 仅由括号 组成，故s中最多只有可能有六种字符素。 此题目是看字符串中是否满足符号匹配问题，所以我们来思考一个问题，就是什么情况下回返回true，什么情况下还会返回false？ 但是若想满足题目条件并返回true，那么有个必要条件就是s 中的素个数为偶数。为什么呢？你想，如果s 正好匹配，那么是不是肯定是一对一对的匹配成功才行，否则有一个多余的，那怎么也不可能返回true，你说对吧？ 好，接下来再看一个问题是：什么情况下匹配错误。 从示例中看，当出现符号交叉时才会出现false，如：[ { ] }。 而且匹配时，都是从左侧最近的素进行匹配，用数组的下标来解释就是：当匹配第5个字符素时，要看第4 个字符素是否和其匹配，而不是看前面的字符。 所以，我们可以用一个栈来存储字符串中的每一个素，然后遍历时，每次取栈顶的素与下一个遍历到的字符进行匹配， 如果匹配成功就将栈顶素pop弹出； 如果匹配失败就将该素放入栈中； 最后遍历完成后，判断栈是否为空即可。 class Solution { public boolean isValid(String s) { int n = s.length(); if((n&1) == 1){ return false; } Stack stack = new Stack(); char[] chs = s.toCharArray(); stack.push(chs[0]); for(int i = 1; i<n; i++){ char top = ‘0’; if(!stack.isEmpty()){ top = (char)stack.peek(); } if((chs[i] == ‘}’ && top == ‘{‘) || (chs[i] == ‘)’ && top == ‘(‘) || (chs[i] == ‘]’ && top == ‘[‘)){ stack.pop(); }else{ stack.push(chs[i]); } } return stack.isEmpty(); } } 还有一个思路是： 用栈存放素，用hashmap来存放映射关系，即“）” 映射“（”，“]”映射“[”，“}”映射“{”。 然后遍历字符串中每一个字符，当前字符，通过map是否包含来判断是否是右符号： 如果是，再判断栈是否为空或者栈顶素是否和当前字符匹配： 如果不匹配就返回false； 如果匹配就弹出栈顶素； 如果不是，则说明是左侧符号，即入栈。 租后判断栈是否为空。 int n = s.length(); if((n&1) == 1){ return false; } Stack stack = new Stack(); Map<Character,Character> map = new HashMap<>(); map.put(‘}’,'{‘); map.put(‘)’,'(‘); map.put(‘]’,'[‘); for(int i = 0; i<n; i++){ char cur = s.charAt(i); if(map.containsKey(cur)){ if(stack.isEmpty() || stack.peek()!=map.get(cur)){ return false; } stack.pop(); }else{ stack.push(cur); } } return stack.isEmpty(); 5、附录： 最后附上我的leetcode提交过程： 
我先是按照第一个思路（去掉奇偶判断）来写的，用了2cms，击败的人数比较少。后来按照思路二击败的就比较多了，但还有一部分。 第一个思路加上奇偶判断后，神了，击败99%+，而且耗时也由2ms变为了1ms。OH， My God! Go fighting! Over……….
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/37668.html
