3
\$\begingroup\$

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("({(())})"));

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can you provide js code example please? I didn't get the idea clearly of your implementation \$\endgroup\$ – Microsmsm Aug 9 '17 at 9:19
  • \$\begingroup\$ I didn't understand from where you got O(n^2) ? ? it's O(n) \$\endgroup\$ – badr aldeen Aug 10 '17 at 8:44
  • \$\begingroup\$ @badr replace is O(n). It's called O(n) times. \$\endgroup\$ – kraskevich Aug 10 '17 at 9:24
2
\$\begingroup\$

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:

  • The complexity is O(n^2) because while is one loop, includes is another, making it a "loop inside a loop" scenario.
  • You will need a lot of tests to make sure every combination is covered, not just the two logs you have.
  • isValid is a vague function name for this functionality. You might want to name it areParensBalanced.
  • Your code is doing unnecessary 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.
  • Your code does not account for anything else other than a parens. Not sure if this is a feature, but just saying.
\$\endgroup\$
2
  • \$\begingroup\$ I don't really understand this line ` if(isCloser && pairs[next] !== stack.pop()) return false` \$\endgroup\$ – Microsmsm Aug 9 '17 at 13:05
  • \$\begingroup\$ @Microsmsm If the next character is a closing parens and the top of the stack (the latest opening parens found) is not a matching open parens (mismatching open and close). array.pop() removes and returns the last item from the array, or in stack terms "the top of the stack". \$\endgroup\$ – Joseph Aug 9 '17 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.