Valid Parentheses leetcode problem using JavaScript

Question

I'm trying to figure out valid parentheses problem from leetcode using JavaScript and I couldn't figure out a plan on how to solve this problem.

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.


Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

My current thinking process is like this:

1. Split the string into an array (example: "{}" --> ["{","}", "[", "]", "(", ")"]
2. Loop through the array
3. Use the index of each characters to compare...?
4. Not sure after this...

Help please.

Answer 1

This is less step code.

var isValid = function(s) {
    backs = {'(':')','{':'}','[':']'}
    remianBacket = [];

    for(let i=0;i<s.length;i++){
        if(remianBacket.length>0 && remianBacket[remianBacket.length-1]==s[i]){
            remianBacket.pop()
        }else if(backs[s[i]]!=undefined){
            remianBacket.push(backs[s[i]]);
        }else{
            return false;
        }
    }

    return remianBacket.length==0;
}

Answer 2

var isValid = function(s) {
    const left = [];
  const legend = {
    '(': ')',
    '{': '}',
    '[': ']'
  };
  for(const char of s) {
    if (char in legend) {
      left.push(char);    
    } else if (legend[left.pop()] !== char) {
      return false;
    }
  }
  return !left.length;
};

Answer 3

• Check if the length of the string is odd. If it is, or if the first bracket is a closing one or the last bracket is an opening one, return false.
• Initialize a stack.
• Loop over each character in the string:
  • If the character is an opening bracket, push it onto the stack.
  • If the character is a closing bracket, check if the top of the stack is matching with its pair. If no match is found, return false.
• After the loop completes, check if the stack is empty. If it is, the string is valid. Otherwise, return false.

var isValid = function(s) {
   
   let dataset = s.split('')
   let length = dataset.length

   if(length%2!=0 ) return false;
   if([')', '}', ']'].includes(dataset[0]) ) return false;
   if(['(', '{', '['].includes(dataset[length-1])) return false;

   let pair = {
       '(':')',
       '{':'}',
       '[':']'
   }
   let stack = []

   for(i=0; i<length; i++)
   {
        if(['(', '{', '['].includes(dataset[i]))
        {
            stack.push(dataset[i])
        }
        else
        {
            let pop_item = stack.pop(dataset[i])
            if(pair[pop_item]!=dataset[i])    return false;
        }
   }

    return stack.length ? false : true; 
};

Answer 4

const isValid = (s) => {
  let stack = [];
  const map = new Map([
    ['(', ')'],
    ['{', '}'],
    ['[', ']'],
  ]);

  for (let i = 0; i < s.length; i++) {
    if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
      stack.push(s[i]);
    } else {
      const last = stack.pop();
      if (s[i] !== map.get(last)) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

Answer 5

Valid Parentheses In Javascript (Asked in many interviews. Simple and accepted solutions.)

Methods used here are string iteration and charAt and replace methods.

var isValid = function(s) {
    let par ={'(' :')','{': '}', '[':']'};
    for(let i=0;i<s.length;++i) {
        if(s.charAt(i+1) && s.charAt(i+1)== par[s.charAt(i)]){
                s = s.replace(s.charAt(i)+s.charAt(i+1),'');
                i=i-2;
        }
    }
    if(s.length){
        console.log(false)
        return false;
    } else {
        console.log(true)
        return true;
    }
};
console.log(isValid("()[]{}"))

Answer 6

const OPENING_BRACKETS = ['(', '[', '{']
const CLOSING_BRACKETS = [')', ']', '}']

const hasBalancedBrackets = text => !countUnmatchedBrackets(text)

function countUnmatchedBrackets(text) {
  return [...text].filter(isBracket).reduce((stack, bracket) =>
    isOpen(bracket) || !isMatch(stack.at(-1), bracket)
      ? /* push */ stack.concat(bracket)
      : /* pop  */ stack.slice(0, stack.length - 1), []).length
}

function isMatch(lastBracket, bracket) {
  return OPENING_BRACKETS.some((openBracket, i) =>
    lastBracket === openBracket &&
    bracket === CLOSING_BRACKETS[i])
}

function isBracket(char) { return isOpen(char) || CLOSING_BRACKETS.includes(char) }
function isOpen(bracket) { return OPENING_BRACKETS.includes(bracket) }

[
  [false, '[){'],
  [true, 'a()a'],
  [true, '{{[([a]a)a]a}}'],
  [false, 'aa{a}a[aa(a](({[{a[[[()(([[a']
].forEach(([expected, input]) =>
  console.assert(expected === hasBalancedBrackets(input), input))

Answer 7

Here's a simple stack implementation:

const BRACKETS = [['(', ')'], ['[', ']'], ['{', '}']];
const OPEN = BRACKETS.reduce((a, [o, c]) => ({...a, [o]: c}), {});
const CLOSE = BRACKETS.reduce((a, [o, c]) => ({...a, [c]: o}), {});

const isBalanced = (s) => {
  const stack = [];
  
  for (const c of [...s]) {
    if (c in OPEN) stack.push(c);
    if (c in CLOSE && stack.pop() !== CLOSE[c]) return false;
  }
  
  return !stack.length;
};

console.log(isBalanced('{{[()]()}}'));
console.log(isBalanced('{[)}'));

I first create two lookup objects for opening and closing brackets. Then it's just a matter of looping over the characters, and:

• if it's an opening bracket, push it onto the stack;
• if it's a closing bracket, pop the last value off the stack and check whether it matches the closing bracket;
• after everything is processed, check that the stack is empty.