MaiDeveloper

Valid Parentheses

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution

/**
 * Validate Parentheses
 * @param {string} s
 * @return {boolean}
 * @time complexity: O(n)
 * @space complexity: O(n)
 */
function isValid(s) {
  const pairs = {
    '(': ')',
    '[': ']',
    '{': '}'
  };
  const stack = [];

  for (let c of s) {
    const opening = pairs[c];

    if (opening) {
      stack.push(opening);
    } else if (c !== stack.pop()){
      return false;
    }
  }

  return stack.length === 0;
}

Test Case

const assert = require('chai').assert;

describe('Valid Parentheses', () => {

  it('should return true when \'()\' is given', () => {
    assert.strictEqual(isValid('()'), true);
  });

  it('should return true when \'()[]{}\' is given', () => {
    assert.strictEqual(isValid('()[]{}'), true);
  });

  it('should return false when \'(]\' is given', () => {
    assert.strictEqual(isValid('(]'), false);
  });

  it('should return false when \'([)]\' is given', () => {
    assert.strictEqual(isValid('([)]'), false);
  });

  it('should return true when \'{[]}\' is given', () => {
    assert.strictEqual(isValid('{[]}'), true);
  });

});
  Valid Parentheses
    ✓ should return true when '()' is given
    ✓ should return true when '()[]{}' is given
    ✓ should return false when '(]' is given
    ✓ should return false when '([)]' is given
    ✓ should return true when '{[]}' is given


  5 passing (13ms)


Mike Mai
Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.