A string s containing only the characters (, ), {, }, [ and ] is given. Determine whether all brackets are balanced.
Every opening bracket must be closed by the same bracket type. Closing brackets must also appear in the correct nested order. Return true for a balanced string and false otherwise.
Example 1
Input: s = "{[()]}"
Output: true
Explanation: Each opening bracket receives a matching closing bracket in reverse order. The innermost pair () closes first, followed by [], then {}.
Example 2
Input: s = "{[(])}"
Output: false
Explanation: Closing bracket ] appears while ( is the latest unmatched opening bracket. The nesting order breaks, so the string is not balanced.
Approach
The latest opening bracket must be closed first, so the solution needs a data structure that returns the most recently stored bracket.
A stack follows the Last-In, First-Out rule, making it suitable for this task. Push every opening bracket into the stack. For each closing bracket, check whether the stack top contains the matching opening bracket.
The string is invalid if the stack is empty or the brackets do not match. After processing all characters, the stack must be empty.
Algorithm
Initialize an empty stack to store unmatched opening brackets.
Traverse every character from left to right.
When an opening bracket appears:
Push the bracket onto the stack.
The latest opening bracket must match the next closing bracket.
When a closing bracket appears:
Return
falseif the stack is empty, because no opening bracket is available for matching.Compare the stack top with the required opening bracket.
Return
falseif the bracket types do not match.Pop the stack when a valid match is found.
After complete traversal, return
trueonly if the stack is empty, because any remaining opening bracket is unmatched.
Dry Run
Balanced Paranthesis
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Checks whether a bracket string is balanced. bool isBalanced(string s) { stack<char> st; // Every character is processed in original order. for (char ch : s) { // Opening brackets wait for a future matching close. if (ch == '(' || ch == '{' || ch == '[') { st.push(ch); continue; } // A closing bracket needs an available opening bracket. if (st.empty()) { return false; } char topBracket = st.top(); // Closing parenthesis must match an opening parenthesis. if (ch == ')' && topBracket != '(') { return false; } // Closing brace must match an opening brace. if (ch == '}' && topBracket != '{') { return false; } // Matching closing and opening square brackets. if (ch == ']' && topBracket != '[') { return false; } // A valid pair is removed from the pending openings. st.pop(); } // Balanced strings leave no unmatched opening bracket. return st.empty(); }};// Driver codeint main() { string s = "{[()]}"; Solution obj; cout << (obj.isBalanced(s) ? "true" : "false") << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N is the length of the string. Each bracket is visited once, and every stack operation takes constant time.
Space Complexity: O(N), because the stack can store all opening brackets when the string begins with only opening brackets.
Interview follow-up Questions
Yes. No unmatched opening or closing bracket exists, so an empty string is considered balanced in the usual definition.
Be the first to add a comment.