LeetCode题目（Python实现）：有效的括号

红太狼 2023-07-13 15:07 20阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  栈
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  另一种
     *   *  算法实现
         *  执行结果
     *  小结

# 题目 #

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

有效字符串需满足：

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

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

**示例1** :

输入: "()"
    输出: true

**示例2** :

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

**示例3** :

输入: "(]"
    输出: false

**示例4** :

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

**示例5** :

输入: "{[]}"
    输出: true

## 想法一 ##

### 算法实现 ###

def isValid(self, s: str) -> bool:
        dic = {
        "}": "{", ")": "(", "]": "["}
        stack = []
        for i in s:
            if i == "(" or i == "{" or i == "[":
                stack.append(i)
            else:
                if len(stack) != 0 and stack.pop() == dic[i]:
                    continue
                else:
                    return False
        return len(stack) == 0

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 40 ms, 在所有 Python3 提交中击败了46.19%的用户  
**内存消耗** : 13.5 MB, 在所有 Python3 提交中击败了5.65%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

## 栈 ##

### 算法实现 ###

def isValid(self, 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

### 执行结果 ###

![在这里插入图片描述][2020031222024996.png]

### 复杂度分析 ###

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

## 另一种 ##

### 算法实现 ###

def isValid(self, s: str) -> bool:
        dic = {
        '{': '}', '[': ']', '(': ')', '?': '?'}
        stack = ['?']
        for c in s:
            if c in dic:
                stack.append(c)
            elif dic[stack.pop()] != c:
                return False
        return len(stack) == 1

### 执行结果 ###

![在这里插入图片描述][20200312220715478.png]

## 小结 ##

先按照自己的想法设计，因为以前做过这道题，所以还有大概的思路，就是用栈来解决，然后自己设计了算法并进行改进，速度都差不多，但是稍微有点不如最后一个的地方：

1.  先判断是否在字典的键中，是就加入，否就继续判断。毕竟字典查找更快。
2.  在栈中提前随便加入一个字符，可以解决中途栈为空时无法pop的问题，从而去除判断栈为空的语句。

**最后一个算法真是令我学到了**，有时候**加点东西可以解决空的问题**，我们总是惯性思维的想要多去除东西而不敢随便乱添加东西，看来要多多拓宽思维。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230529/03d1682bfee5484b897dc7c32b0a2887.png
[2020031222024996.png]: /images/20230529/d758b403dd0342638b3bf7ecb934a561.png
[20200312220715478.png]: /images/20230529/cf00c7c06716487b9a88453e7bdd4d58.png