What is causing this error in leetcode problem

Question

I am solving an easy question but having this error at solving for "()[]{}".

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.

class Solution:
    def isValid(self, s: str) -> bool:
        matchdict = {'(': ')', '{': '}', '[': ']'}
        slen = len(s)
        if slen%2!=0:
            return False
        
        for i in range(slen // 2):
            if (matchdict[s[i]] != s[slen-i-1] and (matchdict[s[2*i]] != s[2*i+1])):
                return False
        
        
        return True

KeyError: ')'
    if (matchdict[s[i]] != s[slen-i-1] and (matchdict[s[2*i]] != s[2*i+1])):
Line 9 in isValid (Solution.py)
    ret = Solution().isValid(param_1)
Line 32 in _driver (Solution.py)
    _driver()
Line 43 in <module> (Solution.py)

The first part of your if statement is insufficient because the matching pair isn't necessarily going to be in the same position relative to the end. Furthermore, it's incorrectly assuming that the first half of the string will only consist of opening brackets. I'm not sure what you're trying to accomplish with the other check that multiplies by 2. I suggest you fundamentally change your approach; a stack data structure would be very useful for this problem. — bgfvdu3w
– bgfvdu3w, Commented Jun 28, 2022 at 22:41
The input can contain very invalid one - such as [ as I can tell. Side note - dont use open function as the variable name. — Daniel Hao
– Daniel Hao, Commented Jun 29, 2022 at 1:22

Mad Physicist · Accepted Answer · 2022-06-29 19:06:48Z

1

Your code is assuming that nothing will be opened after a close bracket. As your simple example shows, the string is not necessarily going to be symmetrical at all. Another simple example is something like (())().

This problem requires a stack, since you need to keep track of a potentially infinite number of mixed brackets. If you only had one type of bracket, a counter would suffice to validate the string. In python, you can keep track of a stack using a list, or slightly more efficiently, a collections.deque.

from collections import deque

close_brackets = {']': '[', ')': '(', '}': '{'}
open_brackets = set(close_brackets.values())

def check(s):    
    stack = deque()
    for c in s:
        if c in open_brackets:
            stack.append(c)
        elif c in close_brackets:
            if not stack or stack.pop() != close_brackets[c]:
                return False
    # If the stack is not empty, you have an unmatched parenthesis
    # somewhere. `not` will convert the result to bool for you.
    return not stack

As an extra bonus, this solution will skip over any non-parenthetical characters, in case you ever want to use it to validate math or something like that.

edited Jun 29, 2022 at 19:06

answered Jun 29, 2022 at 0:31

Mad Physicist

116k29 gold badges202 silver badges292 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Daniel Hao Over a year ago

Good explanations. However, if the input string is ] will get IndexError though.

Daniel Hao Over a year ago

May want to try different variable name than built-in open here.

Mad Physicist Over a year ago

@DanielHao. Good call. Fixed that too

funnydman Over a year ago

if the problem requires a stack, then why do you use deque, if list is enough? I don't see any improvements here over using plain list

Mad Physicist Over a year ago

@funnydman. It's more efficient for this sort of thing: better amortization

|

Collectives™ on Stack Overflow

What is causing this error in leetcode problem

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related