Check If A Parentheses String Can Be Valid - Leetcode Solution

The problem "Check If A Parentheses String Can Be Valid" on LeetCode is a classic problem that involves checking the validity of a parentheses string. The parentheses string consists of opening and closing parentheses and we need to check if the string is valid i.e. the opening and closing parentheses are properly matched.

Solution:

We can use a stack data structure to solve this problem. We will scan the entire string from left to right and for each character in the string, we will perform the following steps:

1. If the current character is an opening parenthesis i.e. '(', we will push it onto the stack.
2. If the current character is a closing parenthesis i.e. ')', we will check if the stack is empty or the top of the stack is not the corresponding opening parenthesis i.e. '('. In either case, the string is invalid and we will return false.
3. If the current character is any other character, we will continue scanning the string.

At the end of the scan, if the stack is empty, it means all opening parentheses have been matched with closing parentheses and the string is valid. Otherwise, the string is invalid.

Here's the code to implement the above algorithm:

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

Time Complexity: O(n), where n is the length of the string.

Space Complexity: O(n), where n is the length of the string. The stack can have at most n elements.

1