大家好,我是程序员吴师兄,今天跟大家分享一道和 有关的题目,超级简单也超级容易理解,这道题目曾经出现在 bilibili 的面试中。

一、题目描述

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

有效字符串需满足:

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

示例 1:

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

示例 2:

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

提示:

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

二、题目解析

我们用 四步分析法 来分析一下这道题目。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1.模拟

有效的情况:

1)不嵌套

2)嵌套

无效的情况:

1)长度为奇数,左括号多余

2)长度为奇数,右括号多余

3)长度为偶数,左括号与右括号不配对

4)长度为偶数,部分子表达式可以配对,但外部不配对

2.规律

通过上述的模拟,可以总结出以下 3 个特点:

  • 1、([]{} 是一一对应的关系,无法配对是无效的
  • 2、对于有效的括号,它的部分子表达式仍然是有效的括号,比如 { [ ( ) ]} ,如果部分子表达式无效,那么整体都是无效的
  • 3、部分子表达式如果建立了配对关系,是有效的括号,那么 消除 后是不会影响整体的
  • 4、奇数长度的字符串总是无效的。

3.匹配

整个过程分为两步,一个是配对,一个是消除。

配对 过程,[]{}

消除 的过程是由内向外进行,先判断能否消除部分子表达式(内),再判断能否消除整体表达式(外),但在遍历的过程却是由外向内进行遍历,需要保存状态, 先进后出的特点符合要求。

4.边界

所谓边界,即特殊情况:

  • 字符串的长度为奇数

三、动画图解

隐藏内容
本内容需权限查看
  • 普通: 5积分
  • 会员: 免费
  • 算法训练营永久会员: 免费

四、参考代码

// 登录 https://www.algomooc.com 查看更多图解
class Solution {

    public boolean isValid(String s) {
        // 当字符串长度为奇数的时候,属于无效情况
        // 条件说明了长度至少为 1,所以不需要在判空
            if (s.length() % 2 == 1) {
               return false;
        }

          //构建栈
        Stack stack = new Stack();

        //由外向内遍历字符串
        for(char c : s.toCharArray()){

            if(c == '('){
               stack.push(')');
            }else if(c == '['){
               stack.push(']');
            }else if( c == '{'){
               stack.push('}');
            }else if( stack.isEmpty() || c != stack.pop()){
            //表明有多余的括号
               return false;
            }
        }
        return stack.isEmpty();
    }
}

五、复杂度分析

时间复杂度

时间复杂度为 O(N)。需要遍历一遍字符串。

空间复杂度

空间复杂度 O(N)。哈希表和栈使用线性的空间大小,最坏情况下,栈的大小将是输入字符串的长度。

六、参考引用

1、https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/

2、https://t10.lagounews.com/aR44RbR+c190C

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。