LeetCode-20 有效的括号
↑点击上面"算法半岛"
关注"算法半岛"第一时间接收最新文章
> 题目：20. 有效的括号
> 难度：简单
> 分类：栈
> 解决方案：入栈出栈
今天我们学习第20题有效的括号，这是一道关于栈的简单题，对熟悉栈的基本使用很有帮助。下面我们看看这道题的题目描述。
题目描述
给定一个只包括 (， )， {， }， [， ] 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"输出: true示例 2:
输入: "()[]{}"输出: true示例 3:
输入: "(]"输出: false示例 4:
输入: "([)]"输出: false示例 5:
输入: "{[]}"输出: true分析
这个题是目前为止遇到的第一个栈相关题目，对于栈不太熟悉的小伙伴可以扫描文章下方的二维码，关注『 算法半岛』回复『 数据结构目录』，即可获得相关学习资料。
对于这个题，我们借助一个栈，遍历字符串时，当遇到 (、 {或 [时，将字符入栈；当遇到 )、 }或 ]时，判断栈顶是否为其对应的左括号，如果对应得上，弹出栈顶元素，如果栈顶为空或则对应不上，则返回 false。对示例5的详细示意图如下所示：
上述分析所对应的 java代码如下所示：
class Solution { public boolean isValid(String s) { // 申请栈 Stack<Character> stack = new Stack<>();
// 将字符串转化为字符数组 char[] chars = s.toCharArray();
for (int i=0; i<chars.length; i++){ // 判断当前字符是否为 '(' 、'[' 或 '{' if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{'){ // 如果时，则入栈 stack.push(chars[i]); }else{ // 如果不是，则为')'、']'或'}''，判断栈顶是否为对应的左括号 if (stack.empty()){ return false; }else{ char c = stack.pop(); if ((chars[i] == ')' && c != '(') || (chars[i] == ']' && c != '[') || (chars[i] == '}' && c != '{')){ return false; } } } }
// 只有当栈为空时，才为true return stack.empty() ? true : false;
}}
Github地址
LeetCode-20 有效的括号：https://github.com/JacobLei/leetcode/blob/master/src/main/java/A20_ValidParentheses.java)
参考链接
有效的括号：https://leetcode-cn.com/problems/valid-parentheses/
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-06-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录