Valid Parentheses | Leetcode 20 | Stack implementation

The Valid Parentheses problem is a classic interview question to check your understanding of stacks and string parsing. It evaluates whether a given string consisting of parentheses—(), {}, [], is well-formed. This guide provides a clear explanation, an easy-to-follow Python solution, and complexity analysis.

Here’s the [Problem Link] to begin with.

Problem Statement

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 are closed by the same type of brackets.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open bracket.

Example

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

Input: s = "(]"
Output: false

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

Intuition & Approach

The problem naturally maps to a stack data structure:

• Every time you see an opening bracket, push it onto the stack.
• When you encounter a closing bracket, pop from the stack and check if it matches the corresponding opening bracket.
• If it matches, continue; otherwise, return false.
• At the end, if the stack is empty, return true (all opened brackets closed properly).

Code Implementation

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for bracket in s:
            # If opening bracket, push to stack
            if bracket in "([{":
                stack.append(bracket)
            else:
                # For closing bracket, stack cannot be empty
                if len(stack) == 0:
                    return False
                
                # Pop last opening bracket and check if matching
                ch = stack.pop()
                if (bracket == ")" and ch == "(") or \
                   (bracket == "]" and ch == "[") or \
                   (bracket == "}" and ch == "{"):
                    continue
                else:
                    return False
        
        # Check if all opened brackets were closed
        return len(stack) == 0

Code Explanation

• The stack stores unmatched opening brackets.
• On encountering an opening bracket ((, {, [), push it onto the stack.
• On encountering a closing bracket (), }, ]), pop the top element from the stack and compare. If mismatched or stack is empty, return False.
• After processing the entire string, if the stack is empty, all brackets matched correctly, return True.

Dry Run Example

Input: "()[]{}"

• ‘(‘ → push → stack: [‘(‘]
• ‘)’ → pop ‘(‘ → matches → continue → stack: []
• ‘[‘ → push → stack: [‘[‘]
• ‘]’ → pop ‘[‘ → matches → continue → stack: []
• ‘{‘ → push → stack: [‘{‘]
• ‘}’ → pop ‘{‘ → matches → continue → stack: []
  End: stack empty → return True

Time and Space Complexity

• Time: O(n), where n is the length of the string. Each character is processed once.
• Space: O(n), stack size can grow to at most n in worst case.

Conclusion

Valid Parentheses is a foundational stack problem that tests your ability to match pairs and manage order efficiently. Understanding this pattern is crucial in interviews and real-world scenarios involving parsing. Practice similar problems like expression evaluation or HTML tag matching to master stack usage.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.