all articles

leetcode war 20 - Valid Parentheses

2017-10-09 @sunderls

leetCode js

https://leetcode.com/problems/valid-parentheses/description/

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

analysis

first some English:

  1. ( ), parenthesis single form, Parentheses plural form
  2. { } Braces ( curly braces)
  3. [ ] Brackets ( square brackets)

now let's see some examples;

  1. for a valid string ()[]{}, we can safely remove () and the rest []{} is still valid
  2. for a nested one ([]{}), we can safely remove [], the un-nested pair, and the rest ({}) is till valid

so we can use a stack and to safely removal

let stack

for each character:
    if left parenthesis:
        push
    if right:
        if matches the previous one:
            remove them both;
        if not
            fail;
            break

tiral 1 - stack to push left parenthesis or pop a pair

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    var stack = [];
    var leftParens = ['(', '{', '['];
    var rightParens = [')', '}', ']'];

    var i = 0;
    var index = 0;
    for (total = s.length; i < total; i++) {
        index = leftParens.indexOf(s[i]);
        if (index > -1) {
            stack.push(s[i]);
        } else {
            index = rightParens.indexOf(s[i]);
            if (index === leftParens.indexOf(stack[stack.length - 1])) {
                stack.pop();                
            } else {
                return false;
            }
        }
    }

    return stack.length === 0;
};

it is fairly simple and passed, but ranked botton 20%. need to be improved.

improval 1

to check matching, we used indexOf, this is slow, we can use object to do direct accessing.

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    var stack = [];
    var leftParens = {
        '(': 1,
        '{': 2,
        '[': 3
    };

    var matching = {
        ')': '(',
        '}': '{',
        ']': '['
    }; 

    for (var i = 0, total = s.length; i < total; i++) {
        if (leftParens[s[i]]) {
            stack.push(s[i]);
        } else {
            if (matching[s[i]] === stack[stack.length - 1]) {
                stack.pop();                
            } else {
                return false;
            }
        }
    }

    return stack.length === 0;
};

and it now ranked top 5%! use more direct accessing!