Valid Parentheses Leetcode Solution

Problem Statement

The Valid Parentheses LeetCode Solution – “Valid Parentheses” states that you’re given a string containing just the characters '(', ')', '{', '}', '[' and ']'. We need to determine whether the input string is a valid string or not. A string is said to be a valid string if open brackets must be closed by the same type of brackets and open brackets must be closed in the same correct order.

Example:

Input:  s = "()"

Output: true

Explanation:

• Open bracket ‘(‘ is closed by the same type of closing bracket ‘)’.

Input:  s = "(]"

Output: false

Explanation:

• Open bracket ‘(‘ is not closed by the same type of closing bracket.

Approach

Idea:

1. The main idea to solve this problem is to use Stack.
2. We’ll maintain a stack of characters and every time we have opening parentheses, we’ll push the same type of closing parenthesis at that position of the stack.
3. When a closing parenthesis is encountered if the stack is non-empty and the stack’s top character must be the same as the current character of the string. If Yes, then continue further otherwise, return false here.
4. After processing all the characters of the string, check if the stack is empty, return true which denotes that the input string is a valid parentheses string otherwise, return false.

Code

Valid Parentheses Leetcode C++ Solution:

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

Valid Parentheses Leetcode Java Solution:

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='('){
          st.push(')');
            }
        else if(c=='{'){
          st.push('}');
            }
        else if(c=='['){
          st.push(']');
            }
            else if(st.empty() || st.pop()!=c){
                return false;
            }
        }
        return st.isEmpty();
    }
}

Complexity Analysis for Valid Parentheses Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since we traverse the entire input string exactly once where N = the total length of the string.

Space Complexity

The space complexity of the above code is O(N). We’re using a stack to store the characters which take O(N) space in the worst case.