Last updated on January 20th, 2025 at 11:12 pm

Here, we see a Valid Parentheses LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Stack, String

Companies

Airbnb, Amazon, Bloomberg, Facebook, Google, Microsoft, Twitter, Zenefits

Level of Question

Easy

Valid Parentheses LeetCode Solution

1. Problem Statement

Given a string s 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.
• Every close bracket has a corresponding open bracket of the same type.

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Stack-based Parentheses Matching”. The stack data structure is used to keep track of opening brackets, and the algorithm ensures that every closing bracket matches the most recent unmatched opening bracket.

3. Code Implementation in Different Languages

3.1 Valid Parentheses C++

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()) return false;
            if(c == ')' && st.top() != '(') return false;
            if(c == '}' && st.top() != '{') return false;
            if(c == ']' && st.top() != '[') return false;
            st.pop();
        }
    }
    return st.empty();
    }
};

3.2 Valid Parentheses Java

class Solution {
    public boolean isValid(String s) {
        HashMap map = new HashMap();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        Stack<Character> stack = new Stack<>();

        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if(c == '(' || c == '{' || c == '['){
                stack.push(c);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                if(map.get(stack.pop()).equals(c)){
                    continue;
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

3.3 Valid Parentheses JavaScript

var isValid = function(s) {
    const stack = [];
    
    for (let i = 0 ; i < s.length ; i++) {
        let c = s.charAt(i);
        switch(c) {
            case '(': stack.push(')');
                break;
            case '[': stack.push(']');
                break;
            case '{': stack.push('}');
                break;
            default:
                if (c !== stack.pop()) {
                    return false;
                }
        }
    }
    
    return stack.length === 0;
};

3.4 Valid Parentheses Python

class Solution(object):
    def isValid(self, s):
        opcl = dict(('()', '[]', '{}'))
        stack = []
        for idx in s:
            if idx in '([{':
                stack.append(idx)
            elif len(stack) == 0 or idx != opcl[stack.pop()]:
                return False
        return len(stack) == 0

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)

• All implementations follow the same logic and have identical time and space complexities.
• The differences in syntax and implementation details (e.g., using a HashMap in Java or a dict in Python) do not affect the overall complexity.
• The stack-based approach ensures efficient validation of parentheses/brackets.