Interview Question
Country: United States
// ZoomBA
config = { '(' : 0 , '{' : 0 , '[' : 0 }
match = { ')' : '(' , '}' : '{' , ']' : '[' }
lfold( string.value ) -> {
c = str($.o)
continue ( c @ config ){ config[c] += 1 }
continue ( !(c @ match) )
config[ match[c] ] -= 1
break ( config[ match[c] ] < 0 )
}
!exists ( config ) :: { $.o.value != 0 }
var pattern = "(){}[]";
var balance = function(s) {
var compareList = [];
for(var i=0; i<s.length; i++) {
// if open char
if(pattern.indexOf(i) % 2 === 0) {
compareList.push(s[i]);
} else {
// if open one exists, remove it
if(compareList.indexOf(s[i-1]) >= 0) {
compareList.splice(compareList.indexOf(s[i-1]),1);
// blow up otherwise
} else {
return false;
}
}
}
return compareList.length === 0;
};
var pattern = "(){}[]";
var balance = function(s) {
var compareList = [];
for(var i=0; i<s.length; i++) {
// if open char
if(pattern.indexOf(i) % 2 === 0) {
compareList.push(s[i]);
} else {
// if open one exists, remove it
if(compareList.indexOf(s[i-1]) >= 0) {
compareList.splice(compareList.indexOf(s[i-1]),1);
// blow up otherwise
} else {
return false;
}
}
}
return compareList.length === 0;
};
c#.
Time O(n).
Space O(1).
A little bit more tricky than solution with stack but it saves running space.
public static bool ValidateBrackets2( string str ) {
const uint n = 0;
// all possible pairs of brackets in forward order
var dic1 = new Dictionary<char, char> { {'{', '}'}, {'(', ')'}, {'[', ']'}, {'<', '>'} };
// all possible pairs of brackets in reverse order
var dic2 = new Dictionary<char, char> { {'}', '{'}, {')', '('}, {']', '['}, {'>', '<'} };
// all possible pairs of brackets coupled
var dic3 = new Dictionary<string, uint> { {"{}", n}, {"()", n}, {"[]", n}, {"<>", n} };
// all possible closing brackets
var dic0 = new Dictionary<char, uint> { { '}', n }, { ')', n }, { ']', n }, { '>', n } };
foreach ( char ch in str ) {
if ( dic1.ContainsKey( ch ) ) {
dic3[ ch.ToString() + dic1[ ch ] ]++;
dic0[ dic1[ ch ] ] = dic0.Values.Max() + 1;
continue;
}
if ( dic2.ContainsKey( ch ) ) {
if ( dic0[ ch ] != dic0.Values.Max() ) { return false; }
try {
checked { dic3[ dic2[ ch ] + ch.ToString() ]--; }
dic0[ ch ] = (dic3[ dic2[ ch ] + ch.ToString() ] == 0)
? 0
: dic0.Values.Where( x => x > 0 ).Min() - 1;
} catch ( OverflowException ) {
return false;
}
}
}
return dic3.All( item => item.Value == 0 );
}
/**
* Javascript Implementation.
* parenthesis-checker
Given an expression string exp, examine whether the pairs and the orders
of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.
For example, the program should print
'balanced' for exp = “[()]{}{[()()]()}” and
'not balanced' for exp = “[(])”
Input:
The first line of input contains an integer T denoting the number of test cases.
Each test case consists of a string of expression, in a separate line.
Output:
Print 'balanced' without quotes if the pair of parenthesis are balanced else print
'not balanced' in a separate line.
*/
function parenthesisChecker(str) {
let stack = [];
const openingParenthesis = ['{','(','['];
const closingParenthesis = ['}',')',']'];
let result = true;
for(let index = 0, length = str.length; index < length; index++) {
const char = str[index];
if(openingParenthesis.indexOf(char) > -1){
stack.push(char);
}
if(closingParenthesis.indexOf(char) > -1){
switch(stack.pop()){
case '{':
result = char === '}';
break;
case '(':
result = char === ')';
break;
case '[':
result = char === ']';
break;
}
// if result is false then immidiately return 'Non balanced'
if(!result) {
return "String is not balanced";
}
}
//console.log("Stack is = " + stack);
}
return 'String is balanced';
}
const str = '[()]{}{[()()]()}';
console.log("parenthesis-checker -> " + parenthesisChecker(str));
My code:
- techinterviewquestion.com February 29, 2016private boolean isValidParenthesis(char[] s) { // assume we have a map contains all type of parenthesis Map<Character, Character> parenthesisType = new HashMap<Character, Character>(); parenthesisType.put('{', '}'); parenthesisType.put('(', ')'); parenthesisType.put('[', ']'); // initial a stack Stack stack = new Stack(); for (int i = 0; i < s.length; i++) { // if s[i] is a valid open parenthesis, push to stack if (parenthesisType.containsKey(s[i])) { stack.push(s[i]); } // if not, this may be a close parenthesis, so // check the top of stack, if it's same type // with s[i], remove this top open parenthesis else if (!stack.empty() && parenthesisType.get(stack.peek()) == s[i]) { stack.pop(); } // if this parenthesis not exist or stack is empty, return false else { return false; } } // if our stack is empty, this mean s is valid parenthesis return stack.isEmpty(); }