20.md

20.Valid Parentheses

Description

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Thinking Process

1. Scan through the string, use a stack to refactor the string following the rules below:
2. If char is an opening parenthesis, just push it onto the stack.
3. If char is a closing parenthesis, check the last element on the stack to see if they match, return false if they don't, pop the last element if they do
4. When one scan of the string is complete, return if the stack is empty

public boolean isValid(String s) {
    Stack<Character> st = new Stack<>();
    
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(c == '(' || c == '[' || c == '{')
            st.push(c);
        else{
            if(st.empty())
                return false;
            if((c == ')' && st.peek() != '(') || (c == ']' && st.peek() != '[') || (c == '}' && st.peek() != '{'))
                return false;
            st.pop();
        }
    }
    return st.empty();
}

Complexity

1. The string is scanned once, time complexity is O(n)
2. A stack can be as large as the string itself, space complexity is O(n)