sol_056.md

Valid Parentheses - Practice - Work@Tech

Given a string with the just the six characters - ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’. Determine if the string is balanced.

A string is balanced if all brackets exist in pairs and are closed in the correct order.

Example:1

Input: 
"({})[]"

Output: 
true

Example:2

Input: 
"{()})("

Output: 
false

Example:3

Input: 
"{(})[]"

Output: 
false

Solution 1

Time - O(n)
Space - O(n)

bool isBalancedParentheses(string str) {
    // add your logic here
	stack<char> s;
	int n = str.size();
	
	for (int i = 0; i < n; i++){
		if (str[i] == '(' || str[i] == '{' || str[i] == '['){
			s.push(str[i]);
		}
		else{
			if (s.empty()) return false;
			else if ((str[i] == ')' && s.top() == '(') || (str[i] == '}' && s.top() == '{') || (str[i] == ']' && s.top() == '[')){
				s.pop();
			}
			else{
				s.push(str[i]);
			}
		}
	}
	return s.empty();
	
}