作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’ 和 ‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例输入:
s = "()" 输出: true 输入: s = "()[]{}" 输出: true 输入: s = "(]" 输出: false
解题思路
下表对比了使用栈、优化的栈方法和递归方法解决有效的括号问题的时间复杂度、空间复杂度以及各自的优缺点：
方法一：栈
栈算法思路：
最直接的方法是使用一个栈。每当我们遇到一个开括号时，我们将其推入栈中。对于每一个闭括号，我们检查栈顶的元素。如果栈顶的开括号与当前的闭括号匹配，我们将其从栈中弹出，否则说明括号无法有效闭合，返回 false。遍历完整个字符串后，如果栈为空，则说明所有括号都有效闭合，返回 true。
代码示例：
def isValid(s: str) -> bool: stack = [] mapping = {")": "(", "}": "{", "]": "["} for char in s: if char in mapping: top_element = stack.pop() if stack else '#' if mapping[char] != top_element: return False else: stack.append(char) return not stack
算法图解
通过使用表格来呈现栈操作的过程可以使理解更加直观。以字符串 s = “([{}])” 为例，我们来详细说明栈操作的过程：
步骤
通过上表可以看出，每一次遇到闭括号时，栈顶的元素正好是与之匹配的开括号，因此该字符串是有效的括号字符串。遍历结束后，栈为空，这意味着所有的括号都被有效匹配。
在上表中，“栈的状态”列表示了在每一步操作之后栈中的元素，“操作”列说明了是将字符入栈还是因为匹配成功而将栈顶元素弹出。
这种使用栈来匹配括号的方法，不仅适用于包含三种括号的情况，同样适用于只包含一种或两种括号的字符串。其关键在于利用栈这一数据结构的特性，即后进先出，来确保括号的顺序和类型都正确匹配。这个过程是解决此类问题的一个典型算法思想。
复杂度分析：
时间复杂度：O(n)，其中 n 是字符串的长度。我们只遍历了一遍字符串。
空间复杂度：O(n)，在最坏的情况下（全部都是开括号），我们将全部字符都放入栈中。
方法二：优化的栈方法
在方法一的基础上，我们可以对栈的使用进行一些优化，以进一步提高算法的效率和简洁性。优化的核心思想是直接在遍历字符串时检查是否为闭括号，如果是，则判断栈顶元素是否为对应的开括号，如果不是或栈为空，则直接返回 false；否则，将栈顶元素弹出。如果遍历完毕后栈为空，则说明所有括号都被正确匹配，返回 true。
优化点：
• 直接映射闭括号到开括号： 通过建立一个从闭括号到开括号的映射，这样可以在遍历字符串时快速检查和弹出栈顶元素。 • 提前返回： 在确定字符串不是有效的括号序列的情况下提前返回，避免不必要的遍历。
代码示例：
def isValid(s: str) -> bool: stack = [] # 闭括号到开括号的映射 mapping = {")": "(", "}": "{", "]": "["} for char in s: if char in mapping: # 如果是闭括号 top_element = stack.pop() if stack else '#' if mapping[char] != top_element: return False # 不匹配则提前返回 else: stack.append(char) # 开括号入栈 return not stack # 栈空说明匹配
算法分析：
时间复杂度： O(n)，其中 n 是字符串的长度。我们只遍历了一遍字符串。
空间复杂度： O(n)，在最坏的情况下（全部都是开括号），我们将全部字符都放入栈中。
方法三：递归解决有效的括号问题
递归方法在解决有效的括号问题时采用的是一种自顶向下的分解策略，通过不断移除字符串中直接相邻的匹配括号对，直到无法继续移除为止。如果最终得到的是一个空字符串，则原始字符串是有效的括号字符串；否则，不是有效的括号字符串。
递归思路基本情况：如果字符串为空，返回 true，表示是有效的括号字符串。
递归步骤：找到第一个匹配的括号对，移除它们，然后对剩下的字符串进行递归判断。
代码示例
def isValid(s: str) -> bool: # 函数用于移除字符串中的一对括号 def removePair(s): pairs = ["()", "{}", "[]"] for pair in pairs: if pair in s: return s.replace(pair, "", 1) # 只替换一次 return s # 递归移除所有括号对 while len(s) > 0: new_s = removePair(s) if new_s == s: # 如果字符串未改变，说明没有括号可以移除 return False s = new_s return True
算法分析
时间复杂度：最坏情况下为 O(n^2)，其中 n 是字符串的长度。每次移除一对括号需要 O(n) 的时间，并且每次移除都要遍历整个字符串。
空间复杂度：由于是递归调用，空间复杂度取决于递归调用的深度，最坏情况下为 O(n)。
优缺点
优点：递归方法直观易懂，能够清晰地表达移除匹配括号对的逻辑。
缺点：效率较低，尤其是在处理较长的字符串时，由于每次递归都需要遍历整个字符串，导致较大的时间和空间开销。
应用场景
有效的括号问题在编程语言的编译器设计、表达式求值等方面都有广泛的应用。例如，编译器在解析代码时需要检查括号是否匹配，以保证代码的结构正确。
结论
有效的括号是一个典型的使用栈解决的问题，通过遍历字符串并利用栈的先进后出的特性来匹配每一种类型的括号。此算法简洁且效率高，适合解决类似的括号匹配问题。
欢迎关注微信公众号 数据分析螺丝钉
