Valid Parentheses

Easy

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type and in the correct order.

Examples

Input	Output
s = "()"	true
s = "([)]"	false

Python Solution

def is_valid(s: str) -> bool:
    stack = []
    pairs = {")": "(", "}": "{", "]": "["}
    for c in s:
        if c in pairs:
            if not stack or stack[-1] != pairs[c]:
                return False
            stack.pop()
        else:
            stack.append(c)
    return len(stack) == 0

JavaScript Solution

function isValid(s) {
  const stack = [];
  const pairs = { ")": "(", "}": "{", "]": "[" };
  for (const c of s) {
    if (pairs[c]) {
      if (!stack.length || stack.pop() !== pairs[c]) return false;
    } else stack.push(c);
  }
  return stack.length === 0;
}

Step-by-Step Explanation

Use a stack to track opening brackets.
For closing brackets, check if the top of the stack matches.
If not, or stack is empty, return false.
At the end, the stack must be empty.

Complexity Analysis

Time	O(n)
Space	O(n)

Related Tools

Regex Tester

All Problems

Two Sum Reverse a String Palindrome Check FizzBuzz Binary Search Reverse Linked List Merge Two Sorted Arrays Maximum Subarray (Kadane's Algorithm)Remove Duplicates from Sorted Array Nth Fibonacci Number Valid Anagram First Unique Character Climbing Stairs Roman to Integer Best Time to Buy and Sell Stock Contains Duplicate Move Zeroes Intersection of Two Arrays Longest Common Prefix