01 Jan 2024•Easy•C++ / Python / TypeScript

Valid Parentheses

Check whether every bracket in a string is closed in the right order.

Problem

Given a string containing only round, square and curly brackets, decide whether it is valid: every opening bracket must be closed by the same type of bracket, in the correct order.

Approach

Use a stack. Push each opening bracket. For each closing bracket, the top of the stack must be the matching opening bracket; pop it if so, and fail otherwise.

The string is valid only if the stack is empty at the end, which catches opening brackets that were never closed.

The solution files below implement this approach in C++, Python and TypeScript.

Complexity

Time: O(n).
Space: O(n) for the stack.

Edge cases

A closing bracket with an empty stack is invalid.
An odd-length string can never be valid, which allows an early exit.
Correct counts in the wrong order, such as a round bracket closed by a square one, are invalid.

Solution files

Python•valid-parentheses/synced-solution.py

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pairs = {')':'(', ']':'[', '}':'{'}
        for c in s:
            if c in '([{': stack.append(c)
            elif not stack or stack[-1] != pairs[c]: return False
            else: stack.pop()
        return not stack

C++•valid-parentheses/synced-solution.cpp

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            if (c=='(' || c=='[' || c=='{') st.push(c);
            else {
                if (st.empty()) return false;
                if (c==')' && st.top()!='(') return false;
                if (c==']' && st.top()!='[') return false;
                if (c=='}' && st.top()!='{') return false;
                st.pop();
            }
        }
        return st.empty();
    }
};

TypeScript•valid-parentheses/synced-solution.ts

function isValid(s: string): boolean {
    const stack: string[] = [];
    const pairs: {[k:string]:string} = {')':'(', ']':'[', '}':'{'};
    for (const c of s) {
        if ('([{'.includes(c)) stack.push(c);
        else if (!stack.length || stack[stack.length-1] !== pairs[c]) return false;
        else stack.pop();
    }
    return stack.length === 0;
}