Understanding the Problem

A given string with brackets have three types of brackets; brackets (), braces {} and squared brackets []. It is to return True if the brackets are paired to open and close in a correct way, like (){}[] or {[()]}. Other strings like [(]) or (() will be considered as not paired so False will be returned.

Approach

I considered using a dictionary with opening of the brackets as keys and closing of the brackets as values, so I would know the opening and closing will pair. Then use a stack to compare the values.

Solution

It was not that easy until I figured out it was all about stack problem. I attempted to solve it with slicing the list from the opening of the bracket to the closing of the bracket then check whether the values at the certain indexes will match, but this one would not solve the test cases completely as it will disregard the brackets in the middle of the list, of the sliced list.

But using stack was the idea, then I wrote code in these steps.

1. If the string has got the odd length or the closing brackets come first, return False

2. Go through for loop, and stack the openings of brackets

3. When the character s[i] is not a opening of a bracket, check it with the last stack if the key and value match one another. If not, return False

4. If the closing bracket s[i] match the opening value from the stack, pop it from the stack

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0:
            return False

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

        stack = []
        for i in range(len(s)):
            if len(stack) == 0 and s[i] not in d.keys():
                return False

            if s[i] in d.keys():
                stack.append(s[i])
            elif s[i] != d[stack[-1]]:
                return False
            else:
                stack.pop()

        if len(stack) != 0:
            return False
        return True

Reflection

It is always a matter of finding the right algorithm to solve a problem. I have got the tendency to spend some time by just coding without thinking much of the intension of the problem, but it is not always working good. I learned again that setting a right algorithm first is necessary though.