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.

• Time : O(n)
• Space : O(1) (constant)

c++

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> pairs {{')','('}, {']','['}, {'}','{'}};
        vector<char> st;
        for(int i = 0; i < s.length() and i <= s.length() - st.size(); i++) {
            if(s[i] == '(' or s[i] == '[' or s[i] == '{') st.push_back(s[i]);
            else {
                if (st.empty() || st.back() != pairs[st[i]]) return false;
                st.pop_back();
            }
        }

        return st.empty();
    }
};