Coder's Cat

## LeetCode: Valid Parentheses

2019-10-21

LeetCode: Valid Parentheses, explanation and solution with C++/Java/Python

Valid Parentheses, explanation and solution with C++/Java/Python. This problem is easy.

## Problem

https://leetcode.com/problems/valid-parentheses/

Given a string 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. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.

Example 1:

## Explanation

There are 3 pair of parentheses:

Think about the case ‘{[]}’, it is not hard to figure out, we need a Stack to store the last valid left part of parentheses, when next char is valid right part, pop out the left part.

Another trivial optimization is, any input just contains these characters, so a valid parentheses string’s length should always be even, we can add a check at the beginning.

Time complexity: $O(N)$, space complexity: $O(N)$.

The worst space complexity happened when the input similar as: ‘((((((((((‘.

## Python

For Python, we can use list replace stack, and also but a dict for clean code.

Preparing for an interview? Checkout this!