面试准备——DSA 第 7 天

Photo by 丹尼尔·埃利亚舍夫斯基 on 不飞溅

今天我们将讨论 有效括号 问题。这个问题常用于理解 Stack 数据结构。

什么是栈：

它是一种线性数据结构，遵循特定的操作执行顺序。它适用于主体 LIFO（后进先出）。

Image borrowed from Programiz

问题：有效括号

给定一个字符串 s 只包含字符 '(' , ')' , '{' , '}' , '[' 和 ']' ，判断输入字符串是否有效。

输入： s = "()[]{}"

输出： 真的

背后的主要思想是如果打开括号，则需要先关闭它，反之亦然。上面的例子是有效的，因为左括号在关闭其他括号之前是关闭的。

输入：s = “({{})}”

输出：假

上面的例子是错误的，因为第一个括号在花括号之前闭合。通过视觉我们可以知道为什么它是无效的，但是为了让计算机验证我们使用堆栈数据结构。

代码：

valid parenthesis code

我们使用字典来存储括号的结果。这是因为它很容易检索并且具有 1 的时间复杂度。堆栈已初始化。

首先，我们遍历字符串并追加到堆栈中，直到找到第一个右括号。当我们找到第一个右括号时，它需要与最近打开的括号匹配。如果匹配，则将其弹出，直到堆栈为空。

如果我们发现任何右括号没有任何开头，或者我们在堆栈中有左括号但没有相应的右括号，那么我们说它无效。如果所有标准都满足，则它是有效的。

时间复杂度：O(n)

空间复杂度：O(1)

感谢您的耐心等待，我很高兴您能学到一些东西。我会带着另一个随机问题回来。

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明

本文链接：https://www.qanswer.top/29410/16021201