Learn how to determine if brackets are balanced or not. This is an actual problem that software developers must occasionally solve and many dev tools have their own implementation of it. We’ll learn how a code editor can pick up our mistakes and highlight exactly which brackets don't match.
Instructions
Given a string, return true if it contains all balanced parentheses ( ) curly- brackets () , and square-brackets [].
Input: String
Output: Boolean
Examples
is8alanced("(x + y) - (4)”); // -> true is8alanced("(((10 ) (}) ((?)(:)))”); // -› true isBalanced("[{()}]”); // -› true is8alanced("(50)(”); // -> false
isBalanced("[{]}”); // -› false
Solution
2 const openstack = [];
3 const open = '([{';
4 const close = ')]}';
5 const matches - {
6 ')': '(',
7 ']': '[',
8 '}': '{'
9 };
10
11 for (let i - 0; i ‹ str.length; i++) (
12 const char str[i]; 13
14 // If it's an open bracket, push it into our array
15 if(open.includes(char)) (
16 openstack.push(char);
17
18 // If it's a close bracket
19 } else if(close.includes(char)) (
20 // pop an item from the open brackets array.
21 const lastopenBracket openStack.pop();
22
23 // If the open and close bracket don't match, return false
24 if(matches[char] !== lastopenBracket) {
25 return false;
26
27
28
29
30 // Ensures there are no characters left on the stack
31 return !openStack.length;
32 }
How it Works
In our for-loop, we process every character. If the current character is an open bracket, we push it onto our openstack array.
If it’s not a bracket, we do nothing.
Once we’re done processing the string, we have to check to make sure there
are no open brackets left on our stack. If there are, our string is unbalanced.
Time
This is a solutiDn with a time complexity Df:
0(n).
Every character is prDcessed in a loop. Inside the lDop, we perform only count-time actions.
Space
The space complexity is:
0(n).
Characters are stored in an array, generally proportional to the size of the input.
Conclusion
There are many ways to skin this cat. Another solution wDuld have been to have two pointers, one at the beginning and one at the end, moving towards the middle. They would be checking to make sure that brackets matched until they met. This would also be an o(n) solution.
Top comments (0)