20. Valid Parentheses

Leetcode #: 20
Name: Valid Parentheses
Difficulty: Easy
Companies asked: Airbnb, Google, LinkedIn, Meta, Twitter
Link: https://leetcode.com/problems/valid-parentheses/

Prompt

You’re given a string s consisted of the following symbols:

'(', ')', '{', '}', '[', ']'

And you need to determine if s is valid. There are 3 rules determining whether if a given string is valid:

1. Open brackets must be closed by the same type of brackets (in other words, an open bracket like ‘{‘ must be closed by the same type of closing bracket so in this case ‘}’.
2. Open brackets must be closed in the correct order so if s is ‘][’, s wouldn’t be valid because the open bracket should be located subsequently to its closed bracket.
3. Every close bracket has a corresponding open bracket of the same type. This means that if s was, for example, ‘{[()]’, this wouldn’t be valid because we don’t have a respective closing bracket for the outer most layer or opening bracket ‘{’.

Approach

We can utilize an auxiliary data structure like a hashmap and store closing symbols as the keys and their respective opening symbols as the values. We’ll also instantiate a variable called stack that will represent a stack data structure.

stack = []
hashmap = {
")":"(",
"}":"{",
"]":"["
}

Next, we want to iterate through each character in the given string or s and at each iteration, check if the character exists as a key in the hashmap. In other words, this conditional will only execute once our current iteration, or character, is a closing bracket. Furthermore, we can set an else statement for this conditional statement above to append the character onto stack if the current iteration, or character, is an opening bracket.

for char in s:
   if char in hashmap:
       # stack.pop() logic
   else:
       stack.append(char)

Once we confirm that the current iteration, or character, is a closing symbol, we want to now check if the stack is not empty and if the last or top most element in the stack is equal to the value of the key of the current iteration, or character, as defined within the hashmap. If this is the case, we’ll go ahead and pop from the stack. Otherwise, we know we have an invalid ordering within the string that violates the 2nd rule above as defined by the problem statement so we’ll ultimately return False.

if stack and stack[-1] == hashmap[char]:
    stack.pop()
else:
    return False

Lastly, once our for-loop iterating through each of the characters in the given s has finished, we’ll return a boolean — True if the stack is empty and False if it is not empty.

return True if not stack else False

Code

Python

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub