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

短命女 2022-10-22 15:57 164阅读 0赞

> 微信公众号：**Java随笔录**  
> 关注可了解更多Java相关的技术分享。问题或建议，欢迎公众号留言！

### 文章目录 ###

*   *   *  题目
         *  解题思路
         *  代码
         *  执行结果
         *  公众号

### 题目 ###

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

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

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。

**示例**：

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

### 解题思路 ###

简单括号匹配问问题，用栈的特性即可解决。

遇到左括号就进栈push，遇到右括号并且栈顶为与之对应的左括号，就把栈顶元素出栈。最后看栈里面 还有没有其他元素，如果为空，即匹配。

需要注意，空字符串是满足括号匹配的，即输出 true。

### 代码 ###

public boolean isValid(String s) { 
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) { 
            char tmp = s.charAt(i);
            if (tmp == '(' || tmp == '[' || tmp == '{') { 
                stack.push(tmp);
            } else if (tmp == ')') { 
                if (stack.isEmpty() || stack.peek() != '(') { 
                    return false;
                }
                stack.pop();
            } else if (tmp == ']') { 
                if (stack.isEmpty() || stack.peek() != '[') { 
                    return false;
                }
                stack.pop();
            } else if (tmp == '}') { 
                if (stack.isEmpty() || stack.peek() != '{') { 
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

### 执行结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70_pic_center]

### 公众号 ###

*  关注公众号，即时接收关于Java的技术分享！

![20210207183855124.JPG][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/f61b0cc8c3a144fdaf1e40dbc4d110bc.png
[20210207183855124.JPG]: /images/20221022/513654b41bb54f3e9fc5a278f080e981.png