leetcode:20.有效的括号

矫情吗；* 2022-02-24 02:42 264阅读 0赞

### 题目描述： ###

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

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

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

###### 示例1： ######

输入: "()"
    输出: true

###### 示例2： ######

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

###### 示例3： ######

输入: "(]"
    输出: false

###### 示例4： ######

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

###### 示例5： ######

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

##### 题目难度：简单 #####

##### 分析： #####

看见这题应该第一时间想到的就是利用栈来解决，也是比较简单的办法，思路：从左到右遍历字符串，如果是左括号`([{`其中一个，那么进行压栈的操作，如果是右括号`)]}`其中一个，则进行弹栈的操作，并判断弹出来的左括号是否和右括号同一类型，即是否成对匹配。如果不匹配直接返回false，匹配则继续。  
代码如下：

class Solution { 
        
        private static Map<Character, Character> map;
        // 初始化一个map用来存放括号，右括号当key，左括号当value，这样遇到右括号需要弹栈的时候比较方便
        public Solution() { 
            map = new HashMap<>();
            map.put(')', '(');
            map.put(']', '[');
            map.put('}', '{');
        }
        
        public boolean isValid(String s) { 
    		// 定义一个栈
            Stack<Character> stack = new Stack<>();
    
            int length = s.length();
            // 如果给定的s是空的直接返回true（测试用例）
            if (s.isEmpty()) { 
                return true;
                // 很容易想到，如果字符串的长度是单数的话，那么肯定不匹配
            } else if (length % 2 == 1) { 
                return false;
            } else { 
            	// 遍历字符串进行压栈和弹栈的操作
                for (int i = 0; i < length; i++) { 
                    char c = s.charAt(i);
                    // 如果是右括号则需要判断栈里是否有相对应的左括号
                    if (map.containsKey(c)) { 
                    	// 这里的“#”号只是用来作为null的替代，如果栈为空，那么“#”号肯定不匹配任何左括号
                        char tempChar = stack.empty() ? '#' : stack.pop();
                        // 如果栈不为null的话，则进行弹栈操作，然后判断是否是一对括号
                        if (tempChar != map.get(c)) { 
                            return false;
                        }
                    } else { 
                    	// 如果是左括号就压栈
                        stack.push(c);
                    }
                }
            }
            // 最后如果栈为空的话，则说明是有效的括号，符合题意
            return stack.isEmpty();
        }
    }

##### 总结： #####

时间复杂度为 O ( n ) O(n) O(n)，只需要一次遍历即可解决问题，缺点是需要进行栈的相关操作，会比数组慢些，优点是比较简单易懂。  
这里不懂栈的相关知识的小伙伴可以找找资料，需要理解什么是压栈和弹栈。