This is a very common interview question. However, this article moves a little advanced as it will not just consider a string of parenthesis (braces or brackets), but a string of any kind of character.
matchingParenthesis("Njoku Samson Ebere")
/*
'No parenthesis found'
*/
matchingParenthesis("{Ebere")
/*
{
'parenthesis should be in two(s)'
*/
matchingParenthesis("}{Njoku] (){{}}Samson Ebere")
/*
}{](){{}}
'Cannot begin with closing parenthesis'
*/
matchingParenthesis("{Njoku{ (Samson) Ebere[")
/*
{{()[
'Cannot end with opening parenthesis'
*/
matchingParenthesis("((() (Samson)")
/*
((()()
'braces do not match'
*/
matchingParenthesis("{(Ebere) [Njoku](Samson)}")
/*
{()[]()}
'All openning brace has a closing brace to match'
*/
Prerequisite
This article assumes that you have basic understanding of javascript's string, array and object methods.
Let's do this!
- filter(), join(), includes(), spread operator, if...statment, for...of, indexOf(), push(), pop()
function matchingParenthesis(string) {
const parenthesis = "(){}[]",
openingParenthesis = "({[",
closingParenthesis = ")}]";
let stack = [];
// extract all parenthesis
let filteredString = [...string].filter((char) =>
[...parenthesis].includes(char)
);
console.log(filteredString.join(""));
// terminate if there is no parenthesis found
if (filteredString.length === 0) return "No parenthesis found";
// terminate if there is just one parenthesis
if (filteredString.length === 1)
return "parenthesis should be in two(s)";
// terminate if it starts with a closing parenthesis
if (closingParenthesis.includes(filteredString[0]))
return "Cannot begin with closing parenthesis";
// terminate if it ends with an opening parenthesis
if (
openingParenthesis.includes(filteredString[filteredString.length - 1])
)
return "Cannot end with opening parenthesis";
// terminate if length is not even number
if (filteredString.length % 2 === 1) {
return "unequal openning and closing tags";
}
// loop through the filteredString
for (char of filteredString) {
// add the current char to the stack if it is an openning brace
if (openingParenthesis.includes(char)) {
stack.push(char);
} else {
let lastStack = stack[stack.length - 1];
// if a closing brace match the last opening brace in the stack,
// pop the last opening brace from the stack
if (
closingParenthesis.indexOf(char) ===
openingParenthesis.indexOf(lastStack)
) {
stack.pop(lastStack);
} else {
return "closing brace does not match opening brace";
}
}
}
if (stack.length !== 0) return "braces do not match";
return "All openning brace has a closing brace to match";
}
- filter(), join(), hasOwnProperty(), split(""), if...statment, for...of, match(), push(), pop()
function matchingParenthesis(string) {
const regEx = /[[\](){}]/gi;
let stack = [];
const parenthesisMap = { "(": ")", "{": "}", "[": "]" };
// extract all parenthesis
let filteredString = string
.split("")
.filter((char) => char.match(regEx));
console.log(filteredString.join(""));
// terminate if there is no parenthesis found
if (filteredString.length === 0) return "No parenthesis found";
// terminate if there is just one parenthesis
if (filteredString.length === 1)
return "parenthesis should be in two(s)";
// terminate if it starts with a closing parenthesis
if (!parenthesisMap.hasOwnProperty(filteredString[0]))
return "Cannot begin with closing parenthesis";
// terminate if it ends with an opening parenthesis
if (
parenthesisMap.hasOwnProperty(
filteredString[filteredString.length - 1]
)
)
return "Cannot end with opening parenthesis";
// terminate if length is not even number
if (filteredString.length % 2 === 1) {
return "unequal openning and closing tags";
}
// loop through the filteredString
for (char of filteredString) {
// add the current char to the stack if it is an openning brace
if (parenthesisMap.hasOwnProperty(char)) {
stack.push(char);
} else {
let lastStack = stack[stack.length - 1];
// if a closing brace match the last opening brace in the stack,
// pop the last opening brace from the stack
if (char === parenthesisMap[lastStack]) {
stack.pop(lastStack);
} else {
return "closing brace does not match opening brace";
}
}
}
if (stack.length !== 0) return "braces do not match";
return "All openning brace has a closing brace to match";
}
Conclusion
Interview questions like this one we just solved tends to test how far you have dived into algorithm. Starting from the basics is very important.
There are many ways to solve problems programmatically. I will love to know other ways you solved yours in the comment section.
Up Next: Algorithm 202: Sock Merchant
If you have questions, comments or suggestions, please drop them in the comment section.
You can also follow and message me on social media platforms.
Thank You For Your Time.
Top comments (2)
These are both good initial implementations to the balanced parentheses problem. Either of these will give the interviewer the opportunity to ask if there are any refactors you would consider for time optimization, memory optimization, readability, modularity, etc., and they like being able to ask that. In fact, some companies will give interviews so intent on "starting with the most straightforward approach" that they'll give you lower consideration for the role you're interviewing for, so this is a really good function to offer as your initial answer.
If your interviewer does ask for refactoring ideas, I noticed a few from when I've answered this question that can apply to your implementation:
The first refactor has to do with sanitizing the input string: Unless an interviewer asks you to remove all of the non-parentheses characters from the input, it's more efficient to skip this. This is because running the input through a regular expression will add at least one extra cycle of iterating through the string to compare each character to the matchable pattern. Since you're already going to compare each character to entries within a map in order to determine what other character they're balanced by, you can lazily filter out the non-parentheses characters there; the map will ask, "What balances the character
'a'? Nothing? Moving right along, then! :D" This makes you lose the opportunity to from the function early if the string isn't an even number of characters long (very clever optimization, by the way!). The tradeoff is that you can check for balanced parentheses running through the entire string exactly once this way. I'm not 100% sure which technique will run faster, but running through the string once is at least less work, theoretically, so I figured it's worth noting.Another detail I noticed is that your implementation checks for proper (
([{}])) nesting in addition to parentheses being balanced (([{)]}). If this is a requirement of the interview problem when you receive it, then there's no reason to switch away from using the stack to check for balance. If nesting isn't important to check for, though, you can use a collection of counters for the opening parenthesis characters, incrementing their values when you iterate over one of them, and decrementing when you see a closing parenthesis. Doing this, you would switch from checking that the closing brace matches the most recent opening brace, and instead return early if any of the counts ever becomes a negative number.Once again, great post! 👍
Hey Josh, I really love the way you broke things down here. I will keep them in mind. Thanks for taking your time to read through.