写点什么

leetcode 20. Valid Parentheses 有效的括号 (中等)

作者:okokabcd
  • 2022 年 8 月 09 日
    山东
  • 本文字数:1368 字

    阅读完需:约 4 分钟

leetcode 20. Valid Parentheses 有效的括号(中等)

一、题目大意

标签: 栈和队列


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


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


有效字符串需满足:


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


示例 1:


输入:s = "()"输出:true


示例 2:


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


示例 3:


输入:s = "(]"输出:false


示例 4:


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


示例 5:


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


提示:


  • 1 <= s.length <= 104

  • s 仅由括号 '()[]{}' 组成

二、解题思路

思路:括号匹配是典型的使用栈来解决的问题。从左向右遍历,每当遇到左括号便放入栈内,遇到右括号则判断其和栈顶的括号是否是统一类型,是则从栈内取出左括号,否则说明字符不串不合法。


实现:遍历字符串,如果栈为空则将当前字符入栈,如果栈顶字符与当前字符匹配则栈顶字符出栈,不匹配当前字符入栈,遍历结束如果栈为空说明字符串合法。

三、解题方法

3.1 Java 实现

public class Solution {    public boolean isValid(String s) {        Stack<Character> stack = new Stack<>();        for (Character c : s.toCharArray()) {            if (isPush(stack, c)) {                stack.push(c);            } else {                stack.pop();            }        }        return stack.isEmpty();    }
private boolean isPush(Stack<Character> stack, Character c) { if (stack.isEmpty()) { return true; }
// {[( boolean isPop = (stack.peek().equals('[') && c.equals(']') || stack.peek().equals('{') && c.equals('}') || stack.peek().equals('(') && c.equals(')')); return !isPop; }}
复制代码

3.2 2014 年的实现

public class Solution {    public boolean isValid(String s) {        if (s == null || s.length() == 0) {            return true;        }        Stack<Byte> ps = new Stack<Byte>();        byte[] bArr = s.getBytes();        boolean isValid = true;        for (byte b : bArr) {            if (!isValid) {                break;            }            switch (b) {            case '(':            case '[':            case '{':                ps.push(b);                break;            case ')':            case ']':            case '}':                if (!ps.empty()) {                    byte tmpB = ps.pop();                    if (tmpB == 40) {                        tmpB++;                    } else {                        tmpB+=2;                    }                    if (tmpB != b) {                        isValid = false;                    }                } else {                    isValid = false;                }                break;            default:                // do nothing            }        }        if (!ps.empty()) {            isValid = false;        }        return isValid;            }}
复制代码

四、总结小记

  • 2022/8/9 一场秋雨一场寒

发布于: 刚刚阅读数: 3
用户头像

okokabcd

关注

还未添加个人签名 2019.11.15 加入

一年当十年用的Java程序员

评论

发布
暂无评论
leetcode 20. Valid Parentheses 有效的括号(中等)_LeetCode_okokabcd_InfoQ写作社区