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)

CodePudding user response：

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 = {']': '[', ')': '(', '}': '{'}
open = set(close.values())

def check(s):    
    stack = deque()
    for c in s:
        if c in open:
            stack.append(c)
        elif c in close:
            if not stack or stack.pop() != close[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.

CodePudding user response：

There is no key in matchdict named ')'.

Is it possible you meant to have the key vals in the opposite order?

ex. matchdict = {')': '(', '}': '{', ']': '['}