validBraces.js

15 Oct 2019 in about Dev on Algorithm

Codewars 알고리즘 풀이

Problem

Write a function that takes a string of braces, and determines if the order of the braces is valid.
- 괄호 문자열을 사용해서, 괄호의 순서가 유효한지를 결정하는 함수를 작성한다.
It should return ‘true’ if the string is valid, and ‘false’ if it’s invalid.
- 문자열이 유효하면 ‘true’를 반환하고, 유효하지 않으면 ‘false’를 반환한다.
All input strings will be nonempty, and will only consist of parentheses, brackets and curly braces: ()[]{}
- 모든 입력 문자열을 비어 있지 않다.
- parentheses (), brackets [], curly braces {}로 구성되어 있다.

Solution 01

function validBraces(braces) {
  while (braces.indexOf('()') !== -1 || braces.indexOf('[]') !== -1 || braces.indexOf('{}') !== -1) {
    braces = braces.replace('()', '').replace('[]', '').replace('{}', '');
  }
  return braces.length === 0 ? true : false;
}

validBraces('()[]{}');  // true
validBraces('([{}])');  // true
validBraces('(]');      // false
validBraces('(}');      // false
validBraces('([)]');    // false
validBraces('[(])');    // false

Solution 02

function validBraces(braces) {
  const open = ['(', '[', '{'];
  const close = [')', ']', '}'];
  let stack = [];
  
  for (let i = 0; i < braces.length; i++) {
    if (open.indexOf(braces[i]) !== -1) {
      stack.push(braces[i]);
    } else if (close.indexOf(braces[i] !== -1)) {
      if (stack[stack.length - 1] === open[close.indexOf(braces[i])]) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
  return stack.length === 0 ? true : false;
}

validBraces('()[]{}');  // true
validBraces('([{}])');  // true
validBraces('(]');      // false
validBraces('(}');      // false
validBraces('([)]');    // false
validBraces('[(])');    // false

Solution 03

function validBraces(braces) {
  const matches = {
    '(': ')',
    '[': ']',
    '{': '}'
  };
  let stack = [];
  
  for (let i = 0; i < braces.length; i++) {
    if (matches[braces[i]]) {
      stack.push(braces[i]);
    } else {
      if (braces[i] !== matches[stack.pop()]) {
        return false;
      }
    }
  }
  return stack.length === 0 ? true : false;
}

validBraces('()[]{}');  // true
validBraces('([{}])');  // true
validBraces('(]');      // false
validBraces('(}');      // false
validBraces('([)]');    // false
validBraces('[(])');    // false

Solution 04

function validBraces(braces) {
  let stack = [];
  
  for (let i = 0; i < braces.length; i++) {
    switch (braces[i]) {
      case '(':
      case '[':
      case '{':
        stack.push(braces[i]);
        break;
      case ')':
        if (stack.pop() !== '(') {
          return false;
        }
        break;
      case ']':
        if (stack.pop() !== '[') {
          return false;
        }
        break;
      case '}':
        if (stack.pop() !== '{') {
          return false;
        }
        break;
    }
  }
  return stack.length === 0 ? true : false;
}

validBraces('()[]{}');  // true
validBraces('([{}])');  // true
validBraces('(]');      // false
validBraces('(}');      // false
validBraces('([)]');    // false
validBraces('[(])');    // false

Solution 05

function validBraces(braces) {
  while (/\(\)|\[\]|\{\}/g.test(braces)) {
    braces = braces.replace(/\(\)|\[\]|\{\}/g, '');
  }
  return !braces.length;
}

validBraces('()[]{}');  // true
validBraces('([{}])');  // true
validBraces('(]');      // false
validBraces('(}');      // false
validBraces('([)]');    // false
validBraces('[(])');    // false