LeetCode每日一题-NO.20-有效的括号

痛定思痛。 2023-09-27 11:47 67阅读 0赞

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

有效字符串需满足：

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

来源：力扣（LeetCode）  
链接：[点击去做题][Link 1]  
![在这里插入图片描述][00b78b10ea20421287681d243ff913c1.png]

import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Map;
    
    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     */
    public class T20 {
        
        public static void main(String[] args) {
        
            String s = "()[]{}";
            boolean valid = isValid(s);
            System.out.println(valid);
        }
    
        public static boolean isValid(String s) {
        
            Map<Character, Character> map = new HashMap<>();
            //定义一个哈希映射，key为右括号]}),值为左括号[{(
            map.put(']', '[');
            map.put(')', '(');
            map.put('}', '{');
    		//定义一个链表，看做栈
            LinkedList<Character> stack = new LinkedList<>();
            //遍历字符数组中每一个字符
            for (char ch : s.toCharArray()) {
        
            //如果第二位遍历到右括号，并且栈中存在与之对应的左括号，则左括号出栈。如果字符数组第一位就是右括号，则无法匹配，直接添加右括号入栈。
                if (stack.size() != 0 && map.containsKey(ch) && (map.get(ch) == stack.getLast())) {
        
                    stack.removeLast();
                } else {
        
                 //如果没有就添加左括号进去，入栈操作
                    stack.addLast(ch);
                }
            }
            //栈空则匹配完成
            return stack.size() == 0;
        }
    }

[Link 1]: https://leetcode.cn/problems/valid-parentheses
[00b78b10ea20421287681d243ff913c1.png]: https://img-blog.csdnimg.cn/00b78b10ea20421287681d243ff913c1.png