20. Valid Parentheses.cpp

/*
Link: https://leetcode.com/problems/valid-parentheses/

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false
Example 4:

Input: "([)]"
Output: false
Example 5:

Input: "{[]}"
Output: true
*/


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

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