首页 > 其他 > 详细

LeetCode 6.有效的括号

时间:2020-02-27 13:02:36      阅读:74      评论:0      收藏:0      [点我收藏+]

题目描述

题目难度:简单

给定一个只包括 ‘(‘,‘)‘,‘{‘,‘}‘,‘[‘,‘]‘ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true


示例 2:

输入: "()[]{}"
输出: true
示例 3:

 

输入: "(]"
输出: false


示例 4:

输入: "([)]"

输出: false


示例 5:

输入: "{[]}"
输出: true

 

解题思路

对于一个字符串,先toCharArray()把它转化成char类型的数组

再使用一个栈来操作;

遍历char数组,对于每一个char有以下情况

(1)假如stack的size为0,则表示之前遍历过的char都能刚好配对,此时如果数组中还有没有遍历的,则直接将其push进stack,继续往下遍历;

(2)假如stack的size不为0,且栈顶的元素和当前遍历到的元素刚好符合“{”“}”或“(”“)”或“[”“]”,则表示当前配对,此时就将栈顶的元素pop出来,继续往下遍历;

(3)假如stack的size不为0,且没有满足第二种情况,则直接将其push进stack,继续往下遍历;

当遍历完整个数组后,如果stack的size刚好为0,则证明是配对的;如果不为0,则当然不配对啦。

技术分享图片

 

 

 技术分享图片

 

 

代码如下

class Solution {
    public boolean isValid(String s) {
           Stack<Character> stack=new Stack<>();
           char[] chars=s.toCharArray();
           for(char aChar:chars){
               if(stack.size()==0){
                   stack.push(aChar);
               }else if(isSym(stack.peek(),aChar)){
                   stack.pop();
               }else{
                   stack.push(aChar);
               }
           }
           return stack.size()==0;
    }
    private boolean isSym(char c1, char c2) {
        return (c1 == ‘(‘ && c2 == ‘)‘) || (c1 == ‘[‘ && c2 == ‘]‘) || (c1 == ‘{‘ && c2 == ‘}‘);
    }
}

 

LeetCode 6.有效的括号

原文:https://www.cnblogs.com/Transkai/p/12371530.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!