Hackerrank - Balanced Brackets Solution
2 min read

Hackerrank - Balanced Brackets Solution

Hackerrank - Balanced Brackets Solution

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

  • It contains no unmatched brackets.
  • The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Given  strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES. Otherwise, return NO.

Function Description

Complete the function isBalanced in the editor below. It must return a string: YES if the sequence is balanced or NO if it is not.

isBalanced has the following parameter(s):

  • s: a string of brackets

Input Format

The first line contains a single integer , the number of strings.
Each of the next  lines contains a single string , a sequence of brackets.

Constraints

  • , where  is the length of the sequence.
  • All chracters in the sequences ∈ { {, }, (, ), [, ] }.

Output Format

For each string, return YES or NO.

Sample Input

3
{[()]}
{[(])}
{{[[(())]]}}

Sample Output

YES
NO
YES

Explanation

  1. The string {[()]} meets both criteria for being a balanced string, so we print YES on a new line.
  2. The string {[(])} is not balanced because the brackets enclosed by the matched pair { and } are not balanced: [(]).
  3. The string {{[[(())]]}} meets both criteria for being a balanced string, so we print YES on a new line.

Solution in Python using stack

def isBalanced(S):
    stack = []
    pairs = {"{": "}", "[": "]", "(" : ")"}
    for i in S:
        if not stack:
            stack.append(i)
        elif i == pairs.get(stack[-1]):
            stack.pop()
        else:
            stack.append(i)
    return "YES" if not stack else "NO"


for i in range(int(input())):
    S = input()
    print(isBalanced(S))

Solution in Python using regex

Not recommended

import re

def isBalanced(s):
    p= "\[\]|\(\)|\{\}"
    while re.search(p,s):
        s = re.sub(p,"",s)
    return "NO" if s else "YES"

for i in range(int(input())):
    print(isBalanced(input()))


Explanation

Basically we are continually using regex to search for (), {} or [] and replace it with an empty string and break the loop once no more such match is found.

If we successfully replace all matches and the resultant value of s is empty string then our function will return "YES".

Example

Loop 1 >>> s = "{[()]}"
Loop 2 >>> s = "{[]}"
Loop 3 >>> s = "{}"
Loop 4 >>> s = ""

If we have a unbalanced parenthesis such as {] then our program will not be able to replace all values of the given string and our function will return "NO".

Loop 1 >>> s = "[[()]{(]}]"
Loop 2 >>> s = "[[]{(]}]"
Loop 3 >>> s = "[{(]}]"

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×