Valid Parentheses

EasyStackvalid-parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']'.

A string s 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.

Return true if s is valid, false otherwise.

Example 1:

Input: s = "()" Output: true

Example 2:

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

Example 3:

Input: s = "(]" Output: false

Recommended time and space complexity

You should aim for a solution with O(n) time complexity and O(n) space complexity, where n is the length of the input string.


Hint 1

A brute force approach would be to check each bracket against every other bracket in the string. This would be an O(n^2) time solution. Can you think of a more efficient approach?


Hint 2

Can you use a data structure that allows you to efficiently check if a bracket is closing and matches the last opened bracket?


Hint 3

We can use a stack to store open brackets. When we encounter a closing bracket, we check if it matches the last opened bracket in the stack.

This problem tests the ability to efficiently determine whether a string consisting of parentheses is valid. It helps develop skills in working with stacks and improves understanding of time and space complexity of algorithms. Solving this problem promotes logical thinking and the ability to optimize code for working with large amounts of data.
solution.js · saved

Input

"()"

Expected Output

true