validParentheses

题目描述

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

思路

• 使用栈方法，遍历字符串
• 如果当前字符为左边括号时，直接将其压入栈
• 如果遇到右半边括号时，分类讨论：
  • 1.如果栈不为空，验证是否对应左边的括号，取出栈顶元素，继续循环、
  • 若这时栈为空，则直接返回false
  • 若不为对应的左边括号，返回false

实现思路

1.使用栈方法（使用数组的push()和pop()来模拟）

代码

var isValid = function(s) {  let valid = true  const stack = []  const mapper = {    '{': '}',    '(': ')',    '[': ']'  }  if (s === '') {    return valid;  }  for (let value of s) {    let v = value;    if (['{', '(', '['].indexOf(v) != -1) {      stack.push(v)    } else {      if (stack.length == 0) {        valid = false;      } else {        const va = stack.pop()        if (mapper[va] != v) {          valid = false;        }      }    }  }  return valid;}