20.有效的括号 (击败leecode 90%用户)

The more you know the more you know you don't know

题目描述

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

有效字符串需满足：

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

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

注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

解题

思路

1. 发现字符串为空时，直接返回true

2. 判断字符串的长度。如果为奇数则直接返回false

3. 将括号的对应关系存入字典中

4. 定义一个列表模拟栈数据结构，当字符为右括号时入栈，当字符串为左括号时候出栈

5. 判断两字符时候相同

代码

class Solution:
    def isValid(self, s: str) -> bool:
        # 是否为空
        if not s:
            return True
        # 是否为奇数
        if len(s) % 2 != 0:
            return False
        # 初始化列表，模拟出栈、入栈
        tmp_list = []
        # 定义括号对应关系
        valid_dict = {
            ")": "(",
            "]": "[",
            "}": "{"
        }
        # 遍历字符串
        for i in s:
            # 如果是左括号则入栈，append到列表的末尾
            if i in ["(", "[", "{"]:
                tmp_list.append(i)
                continue
            # 如果右括号则和列表的末尾对比
            if i in [")", "]", "}"]:
                # 若栈为空，则返回错误
                if not tmp_list:
                    return False
                # 若相同，则从队列中删除末尾的元素
                if tmp_list[-1] == valid_dict[i]:
                    tmp_list.pop()
                    continue
                # 若存在其他字符，直接返回错误
            else:
                return False
        # 返回判断栈是否为空，若空，则返回true，反正返回false
        return not tmp_list

复杂度分析

时间复杂度：O(n)，因为我们一次只遍历给定的字符串长度

空间复杂度：O(n)，最糟糕的情况是所有的字符串都为左括号，此时所有的字符都需要保存到列表中