Back then when I started programming, I hated data structures and algorithms because everyone was saying how you wouldn't invert a binary tree in a real job and similar things. However, once I've learned it, I realized it's actually very helpful and made me think better as a developer. I realized I'm much more flexible in terms of coming up with a solution during development as well as when dealing with DSA.
The Problem?
You're required to check for balanced brackets in an string. A string with balanced brackets means that it has opening brackets of the same type (such as square brackets, angular brackets, and so on) just as much as the closing brackets of the same type. For example, a string contains 99 opening angular brackets ('<') as well as 99 closing angular brackets ('>'). Also, the brackets cannot overlap each other. For example "([)]" is not balanced. In contrast, "{()}[]" is balanced.
The Idea
I don't want to confuse you with all possible solutions. One of the best ways to solve this problem is as follows. We will iterate through the string one time only (big O(n) time) and then depending on the value, we'll do something to solve this problem.
Throughout our journey from first element till the last, we will store all opening brackets (be it angular brackets, square brackets, opening parentheses, and so on) inside a stack. In contrast, when we encounter closing brackets, we will not store them, rather we will pop an item from the existing stack and compare if both these elements are pairs ('<' and '>' are pairs, '[' and ']' are pairs). If yes, everything is good and the string is balanced. If no, the string isn't a balanced expression. I don't want to write so much which might confuse you so I'll show the code snippet in Java to solve this problem. Throughout the code snippet, I will write comments so you'll understand this solution better.
The Implementation
import java.util.*;
class BalancedBrackets {
// We need to store all opening brackets in a list
// and closing brackets in another.
// How do we make sure an opening bracket
// relates with another (such as '<' relates to '>')?
// The way is to put them in the same index in the two lists
// although they are in different lists.
private final List < Character > leftBrackets = Arrays.asList('(', '[', '{', '<');
private final List < Character > rightBrackets = Arrays.asList(')', ']', '}', '>');
public boolean balancedBrackets(String str) {
Stack <Character> stack = new Stack <> ();
<span class="k">for</span> <span class="o">(</span><span class="kt">char</span> <span class="nl">ch:</span> <span class="n">str</span><span class="o">.</span><span class="na">toCharArray</span><span class="o">())</span> <span class="o">{</span>
// if current character is a left bracket, push it to the stack
if (isLeftBracket(ch))
stack.push(ch);
<span class="k">if</span> <span class="o">(</span><span class="n">isRightBracket</span><span class="o">(</span><span class="n">ch</span><span class="o">))</span> <span class="o">{</span>
// If current character is a right bracket, don't push it to the
// stack rather pop an existing item in the stack and compare if
// these two brackets are related to each other. Before that, if
// the stack is empty and the current character is a closing
// bracket, we don't need to do a lot of thinking rather we can
// just return false because for every closing bracket, there must
// be an opening bracket waiting in the stack to be popped.
// Therefore, empty stack means things went wrong, so return false
// immediately.
if (stack.empty())
return false;
<span class="kt">var</span> <span class="n">top</span> <span class="o">=</span> <span class="n">stack</span><span class="o">.</span><span class="na">pop</span><span class="o">();</span>
<span class="k">if</span> <span class="o">(!</span><span class="n">bracketsMatch</span><span class="o">(</span><span class="n">top</span><span class="o">,</span> <span class="n">ch</span><span class="o">))</span>
<span class="k">return</span> <span class="kc">false</span><span class="o">;</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">stack</span><span class="o">.</span><span class="na">empty</span><span class="o">();</span>
}
private boolean isLeftBracket(char ch) {
return leftBrackets.contains(ch);
}
private boolean isRightBracket(char ch) {
return rightBrackets.contains(ch);
}
// This method checks if an opening bracket matches with another
// (for example, '<' matches with '>', '(' matches with ')', and
// so on). For this method to work, we need to make sure each
// index in the two lists hold the brackets of same type. For
// example, at index 2 in first list, if the element is '<', then
// then in index 2 in second list the element must be matching, in
// this case '>'.
private boolean bracketsMatch(char left, char right) {
return leftBrackets.indexOf(left) == rightBrackets.indexOf(right);
}
}
The Reflection
That's how you solve this problem. Let's analyze the time and space complexity of this solution a little. The time complexity is O(n) because we're iterating through every element once. If the string is larger, the time taken to compute the string will be larger linearly. The space complexity is also O(n) because with more brackets, we require additional space linearly to store them.
Top comments (0)