20. Valid Parentheses

Prompt

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

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

And you need to determine if 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 is ‘][’, 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 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 that will represent a stack data structure.

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

Next, we want to iterate through each character in the given string or 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 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 is not empty and if the last or top most element in the 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 from the . 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 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com