开发者社区> 胡哥有话说> 正文

经典面试题:有效的括号

简介: 在前端算法面试中,经常会被问到的一道题是 - “有效的括号”或者是称呼为“字符串是否是括号匹配”,什么意思呢?
+关注继续查看

前言


在前端算法面试中,经常会被问到的一道题是 - “有效的括号”或者是称呼为“字符串是否是括号匹配”,什么意思呢?


判断一个字符串s中,括号是是否是成对、按顺序出现的,如果满足条件返回 true,否则返回false


一个有效的字符串,必需同时满足以下条件:


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


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


举个🌰:


  1. 字符串s = '(a(b)[c])',是有效的,符合上述规则;


  1. 字符串s = '(a{b(})c])',是无效的,虽然都闭合了,但是顺序是不正确的,不符合上述规则;


很多小伙伴在第一次遇到这个问题的时候,都会考虑去进行遍历,查询匹配第一个括号,然后在倒序查询对应的括号,诸如此类的操作,都是南辕北辙,费力不讨好的。


这道面试题非常的基础也非常的经典,主要考察的是面试者对这种数据结构的理解。

如果你想到了这种数据结构,其实这道题就非常简单了。


小课堂:


是一种特殊的逻辑结构,有个特点:在栈中的元素遵循了先进后出,后进先出的特点。


算法实现思路


在字符串遍历的过程中,如果是遇到了左括号,进行入栈操作,如果是遇到了右括号则与当前栈顶元素(即数组的最后一个元素)进行比对,是否是对应匹配的,若匹配,则进行出栈操作,不匹配此刻即可以表示当前字符串不是有效的括号匹配。如果是一直匹配的,执行出栈操作,最终栈内的元素长度肯定是0。我们以字符串s = '(a(b)[c])'举例来说明:


以数组的形式实现栈结构,声明const arr = [],遍历字符串s


  1. 遇到左括号(,执行入栈,则arr = ['(']


  1. 遇到字符a,直接跳到不执行任何操作;


  1. 遇到左括号(,执行入栈,则arr = ['(', '(']


  1. 遇到字符b,直接跳过不执行任何操作;


  1. 遇到右括号),与栈顶元素执行比对,二者是对应的,执行出栈操作,此处arr = ['(']


  1. 遇到左括号[,执行入栈操作,则arr = ['(', '[']


  1. 遇到字符c,直接跳过不执行任何操作;


  1. 遇到右括号],与栈顶元素执行比对,二者是对应的,执行出栈操作,此处arr = ['(']


  1. 遇到右括号),与栈顶元素执行比对,二者是对应的,执行出栈操作,此处arr = []


  1. 判断数组arr的长度为0,得出结果,当前字符串s是有效的括号匹配。


基于以上的逻辑思路,我看来看下代码实现:


/**
 * @method isValid
 * @description 判断字符串s是否是有效括号匹配
 * @param s string 待判断字符串
 * @returns boolean
 */
function isValid(s: string): boolean {
  const len = s.length;
  const arr: string[] = [];
  // 临界值判断
  if (!len) {
    return true;
  }
  // 遍历字符串s
  for (let i = 0; i < len; i++) {
    switch (s[i]) {
      // 左括号 - 入栈
      case '(':
      case '{':
      case '[':
        arr.push(s[i]);
        break;
      // 右括号
      case ')':
        // 比对栈顶元素是(,当前元素是)
        // 不匹配,直接返回false
        // 匹配,执行出栈
        if (arr.pop() !== '(') return false;
        break;
      case '}':
        // 比对栈顶元素是{,当前元素是}
        // 不匹配,直接返回false
        // 匹配,执行出栈
        if (arr.pop() !== '{') return false;
        break;
      case ']':
        // 比对栈顶元素是[,当前元素是]
        // 不匹配,直接返回false
        // 匹配,执行出栈
        if (arr.pop() !== '[') return false;
        break;
      default:
        break;
    }
  }
  return !arr.length;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23523 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
22218 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
18581 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
14689 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
21935 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36339 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15291 0
70
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载