Leetcode|【Leetcode合集】20有效的括号

2023/11/25 Leetcode 共 991 字,约 3 分钟

20. 有效的括号

20. 有效的括号

代码仓库地址https://github.com/slience-me/Leetcode

个人博客https://slienceme.xyz

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

方案1:暴力解

第一种纯暴力解

class Solution {
public:
    bool isValid1(string s) {
        stack<char> st_char;
        for (const auto &item: s){
            if (item=='(' || item=='[' || item=='{'){
                st_char.push(item);
            } else {
                if(!st_char.empty()){
                    char temp = st_char.top();
                    st_char.pop();
                    if (!item) {
                        return false;
                    } else if (item==')' && temp!='('){
                        return false;
                    } else if(item==']' && temp!='['){
                        return false;
                    }else if(item=='}' && temp!='{'){
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        if (st_char.empty()){
            return true;
        } else {
            return false;
        }
    }
};

执行用时分布 4ms 击败35.12%使用 C++ 的用户

消耗内存分布6.47MB 击败57.33%使用 C++ 的用户

方案2:初次优化

优化代码结构

image-20231125120212012

执行用时分布 4ms 击败35.12%使用 C++ 的用户

消耗内存分布6.57MB 击败19.98%使用 C++ 的用户

方案3:再优化

特殊情况立即截断

image-20231125120228950

执行用时分布 0ms 击败100%使用 C++ 的用户

消耗内存分布6.72MB 击败7.68%使用 C++ 的用户

备注:由于有的代码与编辑器冲突,所以改为图片,源代码见github

文档信息

Search

    Table of Contents