C++: Valid Parentheses

Thought Process

The problem involves checking if a string of parentheses is valid or not. A string is valid if all types of parentheses i.e. () , [] , {} are properly closed in the correct order. We use a stack to keep track of opening parentheses. For every closing parenthesis, we check if it matches the most recent opening parenthesis on the stack. If we find a closing parenthesis but the stack is empty or the parentheses don't match, the string is invalid. At the end, if the stack is empty, the string is valid; otherwise, it is invalid. 

class Solution {
public:
    bool isValid(string s) {

        stack<int> st;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
                st.push(s[i]);
            }
            else{
                if(st.empty())
                    return false;

                char ch = st.top();
                if((ch=='(' && s[i]==')') || (ch=='[' && s[i]==']') || (ch=='{' && s[i]=='}'))
                    st.pop();
                else
                    return false;
            }
        }
        if(st.empty())
            return true;
        else
            return false;       
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the string once, where 'n' is the length of the string.

Space Complexity: O(n)

In the worst case, the stack can store up to 'n' elements.

Code copied!