（leetcode每日一题）有效的括号

（leetcode每日一题）有效的括号

• 题目
• 要求
• 思路
• 代码
• 总结

题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

要求

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

思路

• 先入后出正好符合栈的数据结构
• 采用linkedList实现栈

代码

class Solution {
    public boolean isValid(String s) {
       Map<String,String> map = new HashMap<>();
        map.put(")","(");
        map.put("}","{");
        map.put("]","[");

        LinkedList<String> list = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if(map.containsValue(String.valueOf(s.charAt(i)))){
                //插入阶段
                list.addLast(String.valueOf(s.charAt(i)));
            }else{
                String s1 = map.get(String.valueOf(s.charAt(i)));
                if(list.size()>0) {
                    if (list.getLast().equals(s1)) {
                        list.removeLast();
                    } else {
                        return false;
                    }
                }else{
                    return false;
                }
            }
        }
        if(list.size()>0){
            return false;
        }
        return true;
    }
}

总结