有效的括号

港控/mmm° 2022-12-03 05:16 225阅读 0赞

# 有效的括号 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/valid-parentheses/

## 2、题目要求 ##

> **题目描述**

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

有效字符串需满足：

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

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

> **示例 1:**

输入: "()"
    输出: true

> **示例 2:**

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

> **示例 3:**

输入: "(]"
    输出: false

## 3、代码思路 ##

判断括号的有效性可以使用「栈」这一数据结构来解决。

我们遇到左括号时，将左括号入栈；遇到右括号时，将栈顶元素出栈，看看是否与当前的右括号匹配，如果不匹配，则直接返回 `false`

为了能够减少程序的 `if else` 分支，我们使用 `HashMap` 存储右括号与左括号的映射关系，因为遇到右括号时，我们需要去查看栈顶元素是否为对应的左括号，所以 `key` 为右括号，`value` 为左括号

当我们遍历完整个字符串时，此时应判断栈是否为空，如果栈为空，则说明所有括号均匹配完毕，当前字符串为有效的括号字符串，返回 `true`；如果栈不为空，则说明还有剩余的括号没有匹配上，返回 `false`

## 4、代码实现 ##

代码

/**
     * @ClassName ValidBracketDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/1 19:19
     * @Version 1.0
     */
    public class ValidBracketDemo {
        
    
        public static void main(String[] args) {
        
            boolean isValid = isValid("()[]{}");
            System.out.println(isValid);
        }
    
        /**
         * 判断是否为有效的括号
         * @param str   输入的括号字符串
         * @return      true：合法的括号；false：不合法的括号
         */
        public static boolean isValid(String str) {
        
            // 如果字符串长度为奇数，则为非法的括号
            if(str.length() %2 == 1){
        
                return false;
            }
    
            char[] chars = str.toCharArray();
            LinkedList<Character> stack = new LinkedList<>();
            // 因为遇到右括号，我们需要去查看栈顶元素是否为对应的左括号，所以 key 为右括号，value 为左括号
            Map<Character, Character> map = new HashMap<>();
            map.put(')', '(');
            map.put('}', '{');
            map.put(']', '[');
    
            // 遍历字符串中的每一个字符
            for (int i = 0; i < chars.length; i++) {
        
                Character curChr = chars[i];
                // 如果是左括号，则压入栈中
                if (curChr == '(' || curChr == '{' || curChr == '[') {
        
                    stack.push(curChr);
                } else if (stack.isEmpty() || stack.pop() != map.get(curChr)) {
        
                    // 否则如果栈顶元素与右括号不匹配，则返回 false
                    return false;
                }
            }
    
            // 如果栈为空，则说明为有效的括号，如果栈不为空，则说明还多出一些非法的括号
            return stack.isEmpty();
        }
    }