JavaScript solution with a stack


  • 3
    A
    var map = {
        "(": ")",
        "[": "]",
        "{": "}"
    } 
    
    var isValid = function(s) {
        var stack = [];
        
        for (var i = 0; i < s.length; i++) {
            var el = s[i];
            
            if (map[el]) {
                stack.push(map[el]);
            } else {
                if (el !== stack.pop()) {
                    return false;
                }
            }
        }
        
        return stack.length === 0;
    };
    

  • 0

    @alexr another way like this, similar like yours:

    var hashMap = {
        ')': '(',
        ']': '[',
        '}': '{',
    };
    
    var isValid = function(s) {
        if (s.length <= 1) return false;
        var stack = [];
    
        stack.push(s[0]);
        for (var i = 1, l = s.length; i <= l - 1; ++i) {
          var compareItem = stack.pop();
          if (compareItem) {
            if (hashMap[s[i]] !== compareItem) {
                stack.push(compareItem);
            } else {
                continue;
            }
          }
          stack.push(s[i]);
        }
        return stack.length === 0;
    };

  • 0
    R

    I had a similar solution, but added one extra if statement to check for the situation when the stack length is greater than the number of unchecked characters in the string. For example, if the string was '[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]', there is no point in going through the entire string, because just after the mid-point of this string, there are not enough characters left to close the current number of open parentheses in the stack.

    var isValid = function(s) {
      parathenses = {'(': ')','[':']','{':'}'};
      for (var i=0, stack=[]; i<s.length;i++) {
        if (parathenses[s[i]]) stack.push(s[i]);
        else if (s[i] !== parathenses[stack.pop()]) return false;
        if (stack.length > s.length - i) return false;
      }
      return stack.length ? false:true;
    };
    

  • 0
    R

    solid implementation!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.