What do you think of my Algorithm?
I start to eliminate the nearest valid parentheses
and if string.length == 0 so it's valid
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
while (s.length != 0 && s.includes("[]") || s.includes("()") || s.includes("{}")) {
s = s.replace("[]", "");
s = s.replace("()", "");
s = s.replace("{}", "");
}
return s.length < 1
};
console.log(isValid("({((}{}))})"));
console.log(isValid("({(())})"));It's correct, but it's ineffiecent. It uses O(n^2) time in the worst case (for instance, if the input's ((((((..)))))))).
You can do better than that by iterating over the input string and keeping a stack of brackets, pushing opening brackets to it and popping when you encounter closign brackets, checking that it's not empty and that the top bracket matches the current one.
O(n). It's called O(n) times.
\$\endgroup\$
Expanding on the other answer, you can simply loop through the string, keep track of the openers in an array (the stack), and if you find a closer, pop the stack to see if they match.
const openers = {
'{': true,
'[': true,
'(': true,
}
const closers = {
'}': true,
']': true,
')': true,
}
const pairs = {
'}': '{',
']': '[',
')': '(',
}
const areParensBalanced = string => {
for(var stack = []; string.length; string = string.slice(1)){
const next = string.charAt(0)
const isOpener = openers[next]
const isCloser = closers[next]
// If it's not a parens at all
if(!isOpener && !isCloser) return false
// If it's a closer, but there's no more openers in the stack
if(isCloser && !stack.length) return false
// If it's a closer, match it with the recent opener
if(isCloser && pairs[next] !== stack.pop()) return false
// If it's an opener, push it to the stack
if(isOpener) stack.push(next)
}
// We reached the end of the loop but not return.
// Check if the stack has unclosed openers.
return !Boolean(stack.length)
}
console.log(areParensBalanced("({((}{}))})"));
console.log(areParensBalanced("({(())})"));Few things to note in your code:
O(n^2) because while is one loop, includes is another, making it a "loop inside a loop" scenario.isValid is a vague function name for this functionality. You might want to name it areParensBalanced.string.replace() operations when the string might not actually contain what you want to replace. You can at least just loop based on length, and do an if inside to see if that pair exists before doing the replace.
array.pop() removes and returns the last item from the array, or in stack terms "the top of the stack".
\$\endgroup\$