What is balanced parenthesis? It is a set of complete parentheses that has an opening and closing parenthesis For example the following is balanced parenthesis
()()(())((()))
()
(())
The following, however, is not
(()
))((
()))
We can extend this concept to curly braces, square bracket, angle bracket etc. The following is valid
[]({})
[[[{}]]]
<({})><>
The following, however, is not.
<<{{]]]]]
}[[])
There are many coding challenges like this, and on leetcode you can try solving it on your own. Here's my approach with python.
def isValid(self, s: str) -> bool:
sck = []
oc = {
'(': ')',
'{': '}',
'[': ']'
}
ans = True
for char in s:
if char in oc:
sck.append(char)
else:
try: # faster than if statement
ochar = sck.pop()
except IndexError:
ans = False
break
if oc[ochar] != char:
ans = False
if sck:
ans = False
return ans
When I was faced with this challenge I instantly came up with two for loops, but that would give you too much time in time-complexity-wise. But the solution above is free from that issue, because it uses the concept of stack.
The basic of this alogorithm is, when you see one of opening characters ( [ {, you append it to a list. If the character charon iteration is not one of those, extract the last element that was appended by using list.pop(), and compare this with char. If they are not equal, then parentheses are not balanced.
If the list sck is empty, then it means at least one of closing characters ) ] } started in string s, so the parentheses are not balanced. We can check that by try except statement.
If sck has elements remained, that menas there are not enough closing characters that matched opening characters, which means unbalanced parentheses.