We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Parentheses

Difficulty: Easy

Problem Description

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Key Insights

  • Use a stack data structure to keep track of opening brackets.
  • Every time we encounter a closing bracket, check if it matches the top of the stack.
  • If it matches, pop the top of the stack; otherwise, the string is invalid.
  • At the end of the iteration, the stack should be empty if the string is valid.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(n) in the worst case for the stack.

Solution

To solve this problem, we utilize a stack to keep track of opening brackets as we traverse the string. When we encounter a closing bracket, we check if it corresponds to the most recent opening bracket (the one on top of the stack). If it does, we pop the stack; if not, the string is invalid. Finally, we check if the stack is empty to confirm that all opening brackets were properly closed.

Code Solutions

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:  # If it's a closing bracket
            top_element = stack.pop() if stack else '#'  # Get the top element or a dummy value
            if mapping[char] != top_element:  # Check if it matches
                return False
        else:
            stack.append(char)  # If it's an opening bracket, push to stack
            
    return not stack  # Return True if stack is empty
← Back to All Questions