LeetCode20 valid parentheses

Topic describes

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.

A valid string must meet the following requirements:

An open parenthesis must be closed with a close parenthesis of the same type. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string.

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

//
// create a new stack
// 2, scan the string, and push the left parenthesis onto the stack. If the right parenthesis matches the type of the top parenthesis, it will be removed from the stack
If the stack is empty, it is valid, otherwise it is invalid
// 4, VX: mike_fss888 (add friends wow 😝)

var isValid = function (s) {
  if (s.length % 2= = =1) { return false }
  const stack = []
  const map =new Map()
  map.set('('.') ')
  map.set('{'.'} ')
  map.set('['.'] ')

  for (let i = 0, len = s.length; i < len; i++) {
    const c = s[i]
    if (map.has(c)) {
      stack.push(c)
    } else {
      const t = stack[stack.length - 1] // Top of stack element
      if (map.get(t) === c) {
        stack.pop()
      } else {
        return false}}}return stack.length === 0
};

// The title is reprinted from licou official website:
// https://leetcode-cn.com/problems/valid-parentheses/
Copy the code