前言:
如今兄弟们对“c语言栈括号匹配”都比较看重,大家都需要了解一些“c语言栈括号匹配”的相关知识。那么小编也在网摘上搜集了一些关于“c语言栈括号匹配””的相关内容,希望兄弟们能喜欢,兄弟们快快来学习一下吧!题目有效的括号
公众号 《java编程手记》记录JAVA学习日常,分享学习路上点点滴滴,从入门到放弃,欢迎关注
描述
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
示例 4:
输入:s = "([)]" 输出:false
示例 5:
输入:s = "{[]}" 输出:trueSolution解法解题思路
判断有效括号的思路有哪些?
如果s字符串的长度为奇数,则必不可能闭合,可以直接返回false建立缓存映射,KEY为左括号,VALUE为右括号通过利用栈 先入后出的特性非常适合我们这题的思路,如果遇到左括号([({)入栈,在进行右括号(}]))判断时将对应栈顶左括号出栈,最后遍历完栈内数据为空CODE
class Solution { public boolean isValid(String s) { int length = s.length(); //奇数则不可能闭合 if(length%2==1){ return false; } //左括号与右括号的缓存映射 Map<Character,Character> map = new HashMap<>(); map.put('(',')'); map.put('[',']'); map.put('{','}'); Stack<Character> stack = new Stack(); for(int i = 0 ; i < length ; i++){ char c = s.charAt(i); //是否为左括号 if(map.containsKey(c)){ stack.push(c); }else{ //如果是右括号,并且栈深为0,则说明当前的字符串为右括号的字符串,可直接返回false,如 ')' '}' ']' '()())}]' if(stack.size()==0){ return false; } //弹出栈,并且从缓存中获取,对应的右括号与当前字符串相匹配,是否相等,不相等则返回false if(!map.get(stack.pop()).equals(c)){ return false; } } } //最终判断栈深度,为空则说明对撑 return stack.empty(); } }复杂度时间复杂度:O(n),其中 n 是字符串 s 的长度结果执行用时:2 ms, 在所有 Java 提交中击败了76.91%的用户内存消耗:36.8 MB, 在所有 Java 提交中击败了25.12%的用户
我曾在银色平原漫步,也曾在青草之河垂钓,这片土地认识我,我们若不坚强,就将灭亡
标签: #c语言栈括号匹配