美文网首页算法
leetcode第四天 : 有效的括号

leetcode第四天 : 有效的括号

作者: 程序萝 | 来源:发表于2019-06-18 09:50 被阅读0次

    有效的括号

    题目描述

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

    有效字符串需满足:

    1. 左括号必须用相同类型的右括号闭合

    2. 左括号必须以正确的顺序闭合。

    注意空字符串可被认为是有效字符串。

    示例 1:

    输入: "()"
    输出: true
    

    示例 2:

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

    示例 3:

    输入: "(]"
    输出: false
    

    示例 4:

    输入: "([)]"
    输出: false
    

    示例 5:

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

    思路

    ① 首先确定输入的字符串必定为空串或者是括号串

    ② 如果遇到空串直接返回true, 否则如果第一个括号是右单边括号, 直接返回false

    ③ 根据题意, 符合要求的括号串, 必定是成对出现, 否则不满足题意, 示例4是一种非常特殊的情况, 因为它虽然看起来是两对括号匹配的, 实际上在'[)'中已经被判为false, 违反了第二条规则

    ④ 把所有的左单边括号放在栈中, 如果遇到右单边括号, 则需弹出栈顶的左单边括号进行判断

    ⑤ 正确的顺序是指每次遇到右单边括号时, 都要与栈顶的左单边括号相匹配

    ⑥ 编程实现

    例子

    假设括号串为{}()({[]})

    [图片上传失败...(image-e26930-1560822621497)]

    编程

    import java.util.Stack;
    
    /**
     * @author Jack
     * @date 2019-06-16-18:43
     */
    public class Solution {
    
        public static boolean isValid(String s) {
            //切割字符串, 分成一个个单边括号
            String[] split = s.split("");
            Stack stack = new Stack();
            for (int i = 0;i <= split.length -1; i++){
                //判断是否为左边括号
                if(split[i].equals("{")||split[i].equals("[")||split[i].equals("(")){
                    stack.push(split[i]);
                    continue;
                //第一个元素不是左单边括号
                }else if(i == 0){
                    //如果为空串则返回真
                    if ("".equals(split[0])){
                        return true;
                    //右单边括号
                    }else{
                        return false;
                    }
                }else{
                    //判断最后一个元素是右单边括号且栈为空时, 不符合规则, 示例 : "()]"
                    if(i == split.length-1 && stack.empty() && (split[i].equals("}")||split[i].equals("]")||split[i].equals(")"))){
                        return false;
                    }
                    //取出栈顶元素进行判断
                    if(!stack.empty()) {
                        String pop = (String) stack.pop();
                        switch (split[i]){
                            case "}":
                                if("{".equals(pop)){
                                    //如果已经遍历到最后一个元素, 且匹配, 而且没有多余的左单边括号, 则返回true
                                    if(i == split.length -1 && stack.empty()) {
                                        return true;
                                    }
                                    continue;
                                //与栈顶的左单边括号不匹配,返回false
                                }else{
                                    return false;
                                }
                            case "]":
                                if("[".equals(pop)){
                                    if(i == split.length -1 && stack.empty()){
                                        return true;
                                    }
                                    continue;
                                }else{
                                    return false;
                                }
                            case ")":
                                if("(".equals(pop)){
                                    if(i == split.length -1 && stack.empty()){
                                        return true;
                                    }
                                    continue;
                                }else{
                                    return false;
                                }
                            default:
                                return false;
                        }
                    }
                }
            }
            return false;
        }
    
        public static void main(String[] args) {
            System.out.println(isValid(""));
        }
    
    }
    

    成绩

    有效的括号.png

    总结

    说实话, 效率不堪一击, 内存还看得过去, 不过我还是不太懂内存消耗的影响因素是什么, 哈哈哈哈, 感觉自己做出来了就很不错了......看了别人的题解, 感觉自己写的弱爆了, 下面给出别人的简单解法, 太简洁了

    class Solution {
        public boolean isValid(String s) {
            char[] array = s.toCharArray();
            Stack<Character> stack = new Stack<>();
            for (char c : array) {
                if (c =='(' || c =='[' || c =='{') {
                    stack.push(c);
                }else if(stack.isEmpty()){
                    return false;
                }else if (c ==')' && stack.peek()=='(') {
                    stack.pop();
                } else if (c ==']' && stack.peek()=='[') {
                    stack.pop();
                } else if (c =='}' && stack.peek()=='{') {
                    stack.pop();
                }else{
                    return false;
                }
            }
            if(!stack.isEmpty()){
                return false;
            }
            return true;
            
        }
    }
    
    作者:vicyas
    链接:https://leetcode-cn.com/problems/two-sum/solution/zui-pu-tong-de-jie-fa-by-vicyas/
    来源:力扣(LeetCode)
    

    相关文章

      网友评论

        本文标题:leetcode第四天 : 有效的括号

        本文链接:https://www.haomeiwen.com/subject/bhlxqctx.html