EasyNo. 0020

Valid Parentheses — LeetCode 20 Python Solution

Pattern
Stack
Topics
Stack, String
Reading time
2 min

The problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets.

Python solution

PythonSolution
class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        d = {'()', '[]', '{}'}
        for c in s:
            if c in '({[':
                stk.append(c)
            elif not stk or stk.pop() + c not in d:
                return False
        return not stk

Complexity

Time
O(n)
Space · auxiliary
O(n)

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 20. Valid Parentheses is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0071Simplify PathMedium
0224Basic CalculatorHard
0227Basic Calculator IIMedium
0331Verify Preorder Serialization of a Binary TreeMedium
0385Mini ParserMedium
0388Longest Absolute File PathMedium

Frequently asked questions

How hard is LeetCode 20. Valid Parentheses?

LeetCode 20. Valid Parentheses is rated Easy on LeetCode.

What is the time complexity of LeetCode 20. Valid Parentheses?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 20. Valid Parentheses?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 20. Valid Parentheses cover?

LeetCode 20. Valid Parentheses is tagged Stack and String on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.