I first defined a dictionary of the requirements (that being the different parentheses allowed), with an initial value of 0 for each key. I then converted the input to a list. Then for each element in the list, if it exists as a key within the dictionary, then the value of that key will increase by 1. At the end, the corresponding key-values will be compared and 'true' or 'false' will be displayed if there are equal corresponding parentheses - i.e. if the number of '(' == the number of ')'.

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'

When s = "(]", true is displayed instead of false. Please may someone explain why this is happening? It also seems to only be passing 24/91 test cases so there must be a prominent error I can't seem to spot :(

CodePudding user response：

Preamble

You are forgetting several important factors to begin with, regardless of this error. This is a stack problem, meaning that you need to keep track of more than just their counts, instead you need their order as well. See this example:

([)]

Not only are the amount of brackets (U.S. parentheses) equal for each type, but they are also in their corresponding order, i.e. ( is before ), etc. We can get around this by dynamically checking if it is valid, that is to say that we are constantly checking to see if it is valid, rather than running all of our tests at the end.

Planning

Our code needs to do 3 crucial steps:

1. Setting up correspondence dictionaries and creating a stack
2. Iterating through the string, adding an removing from the stack where necessary
3. Final validity checks and extra returns

Setup

We need to create a dictionary to keep track of which opening brackets correspond to closing, and another for closing to opening.

We then need to create a stack. The stack it vital because it tells the user what brackets must be closed and in what order. If we open a new one, we add it to the stack. If we close one, we remove it from the stack. Keep in mind that we can only close the last bracket. If not, then it will be invalid regardless.

Iterating

In the iteration phase, we need to obviously iterate through each character of the string (we can ignore non-bracket characters).

If it is in the opening dictionary, we add it to the stack. If it is in the closed dictionary, we need a little more work to do:

• If the stack it empty and we are trying to remove an item, then the parentheses is obviously invalid. E.g. ()], we cannot close the ] because it was never opened.
• If the bracket is the last element of the stack, then it is valid and we can simply pop it.
• Therefore if it wasn't the last element, then it isn't a valid bracket and we can return that.

Final Checks

Because of all the prior works, we need only 1 check. If the stack is empty, then we have resolved all the parentheses, otherwise we have not. So:

• If empty, return true
• Otherwise, return false This can be achieved through return len(stack) == 0

Code

Don't let this look daunting, I simply added comments and that really filled it out. This code gets a score of approximately 32ms and 14.4MB on LeetCode.

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

Original Error

As it was commented, your original error is partly due to your return statements. True or False are meant to be returned as Booleans, not strings. LeetCode clearly interprets every non-Boolean value in its own respect, namely True (it is very sensitive, you need to give it exactly what it asked for). So, to fix this error, try these returns:

# Swap
return 'true'
# With
return True

# Swap
return 'false'
# With
return False