Loading...
墨滴

Kisrain

2021/09/07  阅读:34  主题:默认主题

Leecode 有效的括号

有效的括号

题目描述

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合

示例 1:

输入:s = "()" 输出:true

示例 2:

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

示例 3:

输入:s = "(]" 输出:false

示例 4:

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

示例 5:

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

思路分析

  1. 我觉得一般涉及到这种类似匹配的问题,可以往栈的方向上思考,如果遇到三种左括号我们就入栈,遇到右括号,就看是否和栈顶匹配,若匹配就将栈顶出栈,不匹配那么说明不符合题意,直接返回false.
  2. 因为要看左括号和右括号是否匹配,所以用字典建立联系
HashMap<Character,Character> map = new HashMap<>();
map.put('{','}');
map.put('[',']');
map.put('(',')');
  1. 代码流程

遍历所有字符,如果遇到左括号,我们就入栈,另外如果栈为空,我们也入栈(如果此时栈为空,且遇到的是右括号,即这种情况s = "))"

否则说明遇到的是右括号,那将栈顶元素取出,并从字典中取出其对应点右括号,看两者是否相等,不等直接返回false;相等就弹出, map.containsKey(temp)是为了防止上面s = "))" 这种情况

for(int i=0;i<chars.length;i++){  //遍历所有字符

            if(chars[i]=='('||chars[i]=='{'||chars[i]=='['||stack.isEmpty()){
                stack.push(chars[i]);
            }else{
                char temp = stack.peek(); //获取栈顶元素
                if(map.containsKey(temp)&&chars[i]==map.get(temp)){ //两者如果相等就弹出
                    stack.pop();
                }else {
                    return false;
                }

            }
        }
  1. 完整代码
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character,Character> map = new HashMap<>();
        map.put('{','}');
        map.put('[',']');
        map.put('(',')');
        char[] chars = s.toCharArray();

        for(int i=0;i<chars.length;i++){

            if(chars[i]=='('||chars[i]=='{'||chars[i]=='['||stack.isEmpty()){
                stack.push(chars[i]);
            }else{
                char temp = stack.peek();
                if(map.containsKey(temp)&&chars[i]==map.get(temp)){
                    stack.pop();
                }else {
                    return false;
                }

            }
        }
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }

    }
}

公众号:扯Coding的蛋

有啥问题大家可以一起交流哈

Kisrain

2021/09/07  阅读:34  主题:默认主题

作者介绍

Kisrain