Python每日一练-----有效的括号

🌧（day30）

目录

📝题目：

题目分析：

解题思路：

🌈代码实现

🌟代码注释

💫pythn骚 *** 作

---

📝题目：

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合
• s 仅由括号 '()[]{}' 组成

⭐示例 1：

输入：s = "()"

输出：true

⭐示例 2:

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

输出：true

⭐示例 3：

输入：s = "(]"

输出：false

⭐示例 4:

输入：s = "([)]"

输出：false

⭐示例 5:

输入：s = "{[]}"

输出：true

题目分析：

题目所说的有效括号和我们平常写代码时所所用括号的有效性是一样的。这也是编译器判断代码括号是否有效的方法之一。

解题思路：

首先，我们知道，如果字符串s中的括号有效，那么字符串s的长度必为偶数，因为奇数不能两两配对。

寻找有效的括号是，我们希望在遇到一个左括号时我们希望在后续遇到和它同类型的右括号，那么我们在遇到这一期望的右括号后我们将配对的左括号取出配对即可，然后重复这一步骤。

对于左括号，我们可以使用栈来存储它（在这里我们不必特意说栈是什么，我们在题解中体会即可。本题中的栈的体现形式为列表）。

那么我们我们是直接将三种类型的左括号直接储存到栈当中吗？

当然不是，我们需要在遍历字符串s的同时进行左括号的储存，和与相同类型右括号的配对。

那么我们怎么知道何时储存左括号？

对此我们可以先将三类括号以右括号为键，左括号为值创建一个字典。如下

dct = {
    ")": "(",
    "]": "[",
    "}": "{",
}

（为什么是右括号为键，左括号为值，带着这个疑问先往下看）

这样，当我们判断遍历到的括号不在字典中时，我们就将它加入到栈中。

值得注意的是，这里说的正在与不在字典的判断依据是字典的键，例如

-----------------------------------------------

dct = {
            ")": "(",
            "]": "[",
            "}": "{",
        }

print('(' in dct)
print(']' in dct)
输出：

False
True
-------------------------------------------------

这就意味着所有的左括号都不在字典dct当中。

🌈代码实现

def isValid(s):
    if len(s) % 2 == 1:
        return False

    dct = {")": "(", "]": "[", "}": "{"}
    stack = list()
    for char in s:
        if char in dct:
            if not stack or stack[-1] != dct[char]:
                return False
            stack.pop()
        else:
            stack.append(char)

    return not stack

🌟代码注释

def isValid(s):
    # 如果字符串长度为奇数，直接返回False
    if len(s) % 2 == 1:
        return False

    # 创建字典
    dct = {")": "(", "]": "[", "}": "{"}
    stack = list()   # 初始化栈stack（为列表）
    for char in s:    # 遍历字符串
        if char in dct:   # 如果遍历到的括号在字典中

            # 判断stack列表是否为空或最后一位是否为同类型右括号
            if not stack or stack[-1] != dct[char]:
                return False  # 不是则返回False
            stack.pop()  # 是则将其拿出匹配（删除）
        else:  # 如果遍历到的括号不在字典中，则将其添加到stack栈（列表）中
            stack.append(char)

    return not stack  # 若两两配对完成，则栈（列表）被取空

在着我们来解答为什么创建字典时右括号为键，左括号为值？

因为在

if not stack or stack[-1] != dct[char]:

一行的判断中，我们想直观的判断字符char的是否为stack[-1]同类型的右括号，如果是，那么dct[char]就等于stack[-1].

对于python我们可以有个骚 *** 作

💫pythn骚 *** 作

我们可以用replace（）函数直接将字符串s中的同类型成对括号“删除”

一般写法

replace（'要替换的值’， '要替换成的值'）

这里我们将同类型成对括号替换成空字符串等同于删除

def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

如果为有效括号那么最终一定可以“删除”完全

今天就到这，明天见。🚀

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄