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

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.