Skip to content

20. Valid Parentheses

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

c++
class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        unordered_map<char, char> labels = {
            {'(', ')'},
            {'[', ']'},
            {'{', '}'}
        };
        for (auto& c : s) {
            if (labels.find(c) != labels.end()) {
                stk.push(c);
            } else {
                if (stk.empty() || labels[stk.top()] != c) {
                    return false;
                }
                stk.pop();
            }
        }
        return stk.empty();
    }
};
go
func isValid(s string) bool {
    var arr []rune
    m := map[rune]rune{
        '(': ')',
        '[': ']',
        '{': '}',
    }
    for _, c := range s {
        if _, ok := m[c]; ok {
            arr = append(arr, c)
        } else {
            if len(arr) == 0 || m[arr[len(arr) - 1]] != c {
                return false
            }
            arr = arr[:len(arr) - 1]
        }
    }
    return len(arr) == 0
}
js
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  var stack = []
  var labels = {
    '(': ')',
    '[': ']',
    '{': '}'
  }

  for (let ch of s) {
    if (labels.hasOwnProperty(ch)) {
      stack.push(ch)
    } else if (stack.length === 0 || labels[stack.pop()] !== ch) {
      return false
    }
  }

  return stack.length === 0
}
py
class Solution(object):

    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack, labels = [], {'(': ')', '[': ']', '{': '}'}
        for ch in s:
            if ch in labels:
                stack.append(ch)
            elif len(stack) == 0 or labels[stack.pop()] != ch:
                return False
        return len(stack) == 0