20. Valid Parentheses

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.

View Leetcode Problem

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();
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.