20. 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:

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.

Example 1:
Input: s = "()"
Output: true

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

Example 3:
Input: s = "(]"
Output: false

Example 4:
Input: s = "([])"
Output: true

Approach

Input: A string s containing only '({[]})'

Output: Determine whether the string is valid

This problem is a typical Valid Parentheses Stack problem.

We use a stack stack to simulate the character processing:

1. Iterate through each character in the string;
2. Before pushing to the stack, first check if the current character is a left parenthesis ([{
   • If it is, directly push it onto the stack.
   • Otherwise, check if the current character matches the symbol at the top of the stack. If there is no top element or it does not match, the string is directly deemed invalid. If it matches, pop the top element.
3. After the traversal is complete, check if there are still unmatched left parentheses remaining in the stack. If there are none left, everything matches and it is valid.

Implementation

python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []  # Stack to hold unmatched left parentheses
        # Bracket pair mapping: Right bracket as key, left bracket as value
        mapping = {')': '(', ']': '[', '}': '{'}

        # Iterate through each character
        for c in s:
            if c in mapping.values():
                # If it is a left bracket, push onto stack
                stack.append(c)
            else:
                # If it is a right bracket, check if it matches the stack top
                if not stack or stack[-1] != mapping[c]:
                    return False  # Stack is empty or mismatch, invalid
                stack.pop()  # Match successful, pop the left bracket from stack top
        
        # Finally, if the stack is empty, it means all brackets matched successfully
        return not stack

javascript

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function(s) {
    const stack = [];

    const map = {')': '(', ']': '[', '}': '{'};

    for (let c of s) {
        if (Object.values(map).includes(c)) {
            stack.push(c);
        } else {
            if (!stack.length || stack.at(-1) !== map[c]) 
                return false;

            stack.pop();
        }
    }

    return !stack.length;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

20. Valid Parentheses (English)

20. 有效的括号 (Chinese)