当 s = "(]" 时，Leetcode 有效括号返回 false？

Question

我首先定义了一个需求字典（允许不同的括号），每个键的初始值为 0。然后我将输入转换为列表。然后对于列表中的每个元素，如果它在字典中作为键存在，则该键的值将增加 1。最后，将比较相应的键值，并 'true' 或 'false' 如果对应的括号相等，则显示 - 即如果“(”的数量 == “)”的数量。

class Solution:
    def isValid(self, s: str) -> bool:
        d = {'(': 0, ')': 0, '{': 0, '}': 0, '[': 0, ']': 0}
        s = list(s)
        
        for i in s:
            if i in d.keys():
                d[i] += 1
                
        if d['('] == d[')'] and d['{'] == d['}'] and d['['] == d[']']:
            return 'true'
        else:
            return 'false'

当 s = "(]" 时，显示 true 而不是 false。请有人解释为什么会这样？它似乎也只通过了 24/91 测试用例，所以一定有一个突出的错误我可以'似乎发现:(

Answer 1

前言

不管这个错误如何，您都忘记了几个重要的开始因素。这是一个 stack 问题，这意味着您不仅需要跟踪它们的数量，还需要跟踪它们的顺序。看这个例子：

([)]

不仅每种类型的括号（U.S.括号）的数量相等，而且它们的顺序也相应，即(在)之前，等等. 我们可以通过动态检查它是否有效来解决这个问题，也就是说我们不断地检查它是否有效，而不是运行我们所有的测试都在最后。

规划中

我们的代码需要执行 3 个关键步骤：

设置对应字典并创建堆栈
遍历字符串，在必要时添加从堆栈中删除
最终有效性检查和额外的 returns

设置

我们需要创建一个字典来跟踪哪些左括号对应于右括号，另一个用于右括号对应于左括号。

然后我们需要创建一个堆栈。栈很重要，因为它告诉用户必须关闭哪些括号以及以什么顺序关闭。如果我们打开一个新的，我们将它添加到堆栈中。如果我们关闭一个，我们将其从堆栈中删除。请记住，我们只能关闭 最后一个括号 。如果没有，那么无论如何都是无效的。

迭代

在迭代阶段，我们显然需要遍历字符串的每个字符（我们可以忽略非括号字符）。

如果在开字典中，我们就把它加入栈中。如果它在封闭字典中，我们需要做更多的工作：

如果堆栈为空，而我们正试图删除一个项目，那么括号显然是无效的。例如。 ()]，我们无法关闭 ]，因为它从未打开过。
如果括号是堆栈的最后一个元素，那么它是有效的，我们可以简单地pop它。
因此，如果它不是最后一个元素，那么它就不是一个有效的括号，我们可以 return 那。

最终检查

由于之前的所有工作，我们只需要 1 个检查。如果堆栈为空，那么我们已经解决了所有的括号，否则我们没有。所以：

如果为空，return为真
否则，return错误这可以通过 return len(stack) == 0

代码

不要让这看起来令人生畏，我只是简单地添加了评论，这真的填满了它。此代码在 LeetCode.

上获得了大约 32ms 和 14.4MB 的分数

class Solution:
    def isValid(self, string: str) -> bool:
        
        # Setup
        stack = []
        
        opening = {"(":")","[":"]","{":"}"}
        closing = {")":"(","]":"[","}":"{"} 
        # Closing not needed for correspondence, but
        # helpful for checking if it is a closing bracket
        
        # Iteration
        for char in string:
            
            # Opening bracket, add to list
            if char in opening:
                stack.append(opening[char])
            
            # Closing bracket, extra checks
            elif char in closing:
                
                # Empty, cannot close and thus false
                if len(stack) == 0:
                    return False
                
                # It last element, therfore valid bracket
                elif char == stack[-1]:
                    stack.pop()
                
                # Not last element, invalid
                else:
                    return False
        
        # Final validity statement
        return len(stack) == 0

原始错误

如评论所述，您最初的错误部分是由于您的 return 陈述造成的。 True 或 False 意味着 returned 作为布尔值，而不是字符串。 LeetCode 清楚地解释了每个非布尔值本身，即 True （它非常敏感，你需要准确地给出它所要求的）。因此，要修复 this 错误，请尝试这些 returns:

# Swap
return 'true'
# With
return True

# Swap
return 'false'
# With
return False

当 s = "(]" 时，Leetcode 有效括号返回 false？

Leetcode Valid Parentheses returning false when s = "(]"?

python

debugging

dictionary

前言

规划中

设置

迭代

最终检查

代码

原始错误