This the frequently asked question in FANG & Top Rated Leet Code Problem.. solution in Java.

Approach-1 : Time Complexity : O(n) & Space: O(n).

This problem is to check how much good you are at data structures. Best Data Structure to solve this problem is Stack or ArrayDeque(In Java) faster than Stack. To validate current char I used switch-case instead of if-else

import java.util.Stack;/**
*
* @author SivaReddy Uppathi
*/
public class BalancedParathesis {
// Approch-1
private static boolean isBalanced(String expression) {
// ArrayDeque is faster than Stack class
// Deque<Character> stack = new ArrayDeque<>();
Stack<Character> paranthasis = new Stack<>();
if (expression.isEmpty()) {
return true;
}
for (int i = 0; i < expression.length(); i++) {
char current = expression.charAt(i);
if (current == '(' || current == '{' || current == '[') {
paranthasis.add(current);
continue;
}
if (paranthasis.empty()) {
return false;
}
char lastchar;
switch (current) {
case '}':
lastchar = paranthasis.pop();
if (lastchar == '(' || lastchar == '[') {
return false;
}
break;
case ')':
lastchar = paranthasis.pop();
if (lastchar == '{' || lastchar == '[') {
return false;
}
break;
case ']':
lastchar = paranthasis.pop();
if (lastchar == '{' || lastchar == '(') {
return false;
}
break;
}
}
return paranthasis.empty();
}
public static void main(String[] args) {
String str = "{a[b(g)]q}";
boolean balanced = isBalanced(str);
System.out.println(balanced);
}
}

Approach-2 : Time Complexity : O(n) & Space: O(n).

It is also same as Approach 1 but the difference is Using if-else. This is a Short form of above one.

private static boolean isBraceBalanced(String braces) {       Stack<Character> stack = new Stack<>();       for (char c : braces.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if ((c == ')' && (stack.isEmpty() || stack.pop() != '('))
|| (c == ']' && (stack.isEmpty() || stack.pop() != '['))
|| (c == '}' && (stack.isEmpty() || stack.pop() != '{'))) {
return false;
}
}
return stack.isEmpty();
}

Full Stack Software Developer| Programming enthusiast | Loves DS-Algo and System Design

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