LeetCode 20: Valid Parentheses Solution

Master LeetCode problem 20 (Valid Parentheses), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

20. Valid Parentheses

Easy

String Stack

Problem Explanation

Explanation

To solve this problem, we can use a stack data structure. We iterate through the characters of the input string s and for each character:

If it is an opening bracket, we push it onto the stack.
If it is a closing bracket, we check if the stack is empty or if the top of the stack does not correspond to the matching opening bracket. If either condition is true, we return false.
If all characters are processed and the stack is empty, we return true; otherwise, we return false.

Time complexity: O(n) where n is the length of the input string s. Space complexity: O(n) in the worst case where all characters are opening brackets.

Solution Code

import java.util.Stack;

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 20 (Valid Parentheses)?

This page provides optimized solutions for LeetCode problem 20 (Valid Parentheses) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 20 (Valid Parentheses)?

The time complexity for LeetCode 20 (Valid Parentheses) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 20 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 20 in Java, C++, or Python.

Back to LeetCode Solutions