# 20. Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
    
2. Open brackets must be closed in the correct order.
    
3. Every close bracket has a corresponding open bracket of the same type.
    

### Thoughts

* My immediate thought is that this problem is possible with some weird recursion-y thing
    
    * Although I imagine that this isn't super efficient as you have to perform many substring operations
        
    * nvm recursion is dumb for this
        
* I think a stack works better here
    

### Solution

```java
class Solution {
    public boolean isValid(String s) {
        if (s.length() <= 1) return false;
        Stack<Character> stack = new Stack();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.size() != 0) {
                    char c2 = stack.peek();
                    if (c == ')' && c2 == '(') stack.pop();
                    else if (c == '}' && c2 == '{') stack.pop();
                    else if (c == ']' && c2 == '[') stack.pop();
                    else return false;
                } else return false;

            }
        }

        if (stack.size() == 0) return true;
        return false;
    }
}
```

**Time Complexity:** O(n)  
**Space Complexity:** O(n)

### Conclusion

This took embarrassingly long for me to figure out for some reason. I definitely need to do more of these types of questions because the amount of time I just sank into this problem is simply ridiculous. Really the biggest part was actually accounting for the *invalid* cases, such as a string starting with a closing parenthesis or a string being only one parenthesis. Basically I need to work on better edge case detection when I am reading these questions and doing more thinking before I actually get started on writing my solutions.