Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Balanced Brackets (Main Thread)

Here is the interview question prompt, presented for reference.

As a software engineer, you'll often be asked to optimize programs. One of the easiest ways to do so is by the introduction of an additional data structure.

Here's another classic problem along the same vein. We're provided a string like the following: "{[])}" that is inclusive of the following symbols:

  1. parentheses '()'
  2. brackets '[]', and
  3. curly braces '{}'.

Can you write a function that will check if the symbol pairings in the string follow these below conditions?

  1. They are correctly ordered, meaning opening braces/symbols should come first.
  2. They contain the correct pairings, so every opening brace has a closing one.
  3. They are both of the same kind in a pair, so an opening parenthesis does not close with a closing curly brace.

For example, () is valid. (( is not. Similarly, {{[]}} is valid. [[}} is not.

Constraints

  • Length of the string <= 100000
  • The string will only consist of characters like [,],{,},(,)
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked almost 7 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Balanced Brackets.

daviton Commented on Jan 18, 2021:

Hello

Just want to mention that the code seems to have issues, it dosent pass all the test cases in leetcode, here is how i made it work
class Solution:
def isValid(self, s: str) -> bool:
mystk = []
paren = {'[': ']',
'(': ')',
'{': '}'
}
openpar = 0
for item in s:
if item in paren:
mystk.append(item)
openpar += 1
elif item in paren.values() and openpar == 0:
return False
else:
close = mystk.pop()
if paren[close] != item:
return False
openpar -= 1
if len(mystk) == 0:
return True
else:
return False