# [LeetCode] Top Interview 150 Problems Solving # 20 Valid Parentheses

# **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
    

```python
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.