Search code examples
javascriptparentheses

Leetcode solution works on my computer but not on website (Valid Parenthesis)


I'm fairly new to leetcode and am getting a wrong result for my solution to this problem but I don't see any obvious problems with it. When I run the code on my computer on the question it is failing on it works but on the site it gives the wrong result.

const leftBrackets = ["(", "{", "["];
const matchBrackets = { ")": "(", "}": "{", "]": "[" };
const testStack = [];

var isValid = function (s) {
  for (const char of s) {
    if (leftBrackets.includes(char)) {
      testStack.push(char);
    } else if (testStack[testStack.length - 1] === matchBrackets[char]) {
      testStack.pop();
    }
  }

  if (testStack.length === 0) return true;
  else return false;
};

This is the question: https://leetcode.com/problems/valid-parentheses/submissions/

This is my answer to the question. When I run it the site says the code got the wrong result for "{[]}" as the input. It says it returns false, but when I run it in NodeJS on my computer it returns true. Does anyone know why this happens? I just want to be able to verify when I have got the solution to a problem. I'd also like feedback on my solution if you are answering anyway. I'm trying to make my solutions more efficient without resorting to just looking everything up. This seems like it should be possible easily with O(n).

Thanks to anyone that answers!

EDIT: I added my full solution below in the off-chance someone working on this question sees this post. It did very well on the speed thing (56ms, faster than 98%) so I think its pretty efficient. It also seems to be random how long it takes lol.

var isValid = function (s) {
  
  const leftBrackets = ["(", "{", "["];
  const matchBrackets = { ")": "(", "}": "{", "]": "[" };
  const testStack = [];
  
  if (s.length % 2 !== 0) return false;
  
  for (const char of s) {
    if (leftBrackets.includes(char)) {
      testStack.push(char);
    } else if (testStack[testStack.length - 1] === matchBrackets[char]) {
      testStack.pop();
    } else return false;
  }
  
  if (testStack.length === 0) return true;
  else return false;
};

Solution

  • You probably just need to move the testStack inside the function, otherwise it'll persist for all calls of isValid. Here's another false negative example:

    const leftBrackets = ["(", "{", "["];
    const matchBrackets = { ")": "(", "}": "{", "]": "[" };
    const testStack = [];
    
    var isValid = function (s) {
      for (const char of s) {
        if (leftBrackets.includes(char)) {
          testStack.push(char);
        } else if (testStack[testStack.length - 1] === matchBrackets[char]) {
          testStack.pop();
        }
      }
    
      if (testStack.length === 0) return true;
      else return false;
    };
    
    console.log(isValid('('));
    console.log(isValid('[]'));

    So just do

    var isValid = function (s) {
      const testStack = [];
    

    so that each invocation has its own array.

    Your question doesn't include the problem description, but a potential bug is that you're not checking whether the wrong right bracket is used. For example, if you want the string

    (])
    

    to fail, you'll need to change your logic - either push or pop, and if neither condition is satisfied, perhaps you want to return false.