20. Valid Parentheses

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

O(N) Time and O(N) Space, straightforward solution

• if the string is empty, return true
• if the string has an odd number of characters, return false
• Create a stack to store parenthesis.
• if character is any opening parenthesis, push it to the stack
• after first if, if stack is empty, which means the character is closing parenthesis, return false
• else
  • current character is matching parenthesis of top char of stack, pop that opening character from stack.
  • else push it in the stack.
• return true if stack is empty else false.

Code

class Solution{
public:
    bool isValid(string s){
        stack<char> st;
        int n = s.size();
        if ((n & 1))
            return false;
        for (int i = 0; i < n; i++){
            if (s[i] == '(' || s[i] == '[' || s[i] == '{'){
                st.push(s[i]);
            }
            else{
                if (st.empty()) return false;
                if ((s[i] == ')' && st.top() == '(') || (s[i] == ']' && st.top() == '[') || (s[i] == '}' && st.top() == '{')){
                    st.pop();
                }else{
                    st.push(s[i]);
                }
            }
        }
        return st.empty();
    }
};

Some slight simplification

• we don’t need to push extra closing parenthesis in the stack, if extra parenthesis appears return false.

Code

class Solution{
public:
    bool isValid(string s){
        stack<char> st;
        int n = s.size();
        if ((n & 1)) return false;
        for (int i = 0; i < n; i++){
            if (s[i] == '(' || s[i] == '[' || s[i] == '{'){
                st.push(s[i]);
            }
            else{
                if (st.empty() || (s[i] == ')' && st.top() != '(') || (s[i] == ']' && st.top() != '[') || (s[i] == '}' && st.top() != '{'))
                    return false;
                st.pop();
            }
        }
        return st.empty();
    }
};

Code

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto x: s){
            if(x == '('||x == '['||x == '{')
                st.push(x);
            else{
                if(st.empty())
                    return false;
                char c = st.top();
                st.pop();
                if(c == '(' && x != ')')
                    return false;
                if(c == '[' && x != ']')
                    return false;
                if(c == '{' && x != '}')
                    return false;
            }
        }
        return st.empty();
    }
};