有效的括号

[Cosen95]

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

[Cosen95]

题目难度easy，涉及到的算法知识有栈、哈希表。

题目描述

给定一个只包括'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

1、左括号必须用相同类型的右括号闭合。 2、左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

思路分析

这道题可以利用栈结构。

思路大概是：遇到左括号，一律推入栈中，遇到右括号，将栈顶部元素拿出，如果不匹配则返回 false，如果匹配则继续循环。 第一种解法是利用switch case。

switch case

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let arr = [];
    let len = s.length;
    if(len%2 !== 0) return false
    for(let i = 0; i<len;i++) {
        let letter = s[i];
        switch(letter) {
            case '(': {
                arr.push(letter);
                break;
            }
            case '{': {
                arr.push(letter);
                break;
            }
            case '[': {
                arr.push(letter);
                break;
            }
            case ')': {
                if(arr.pop() !== '(') return false
                break;
            }
            case '}': {
                if(arr.pop() !== '{') return false
                break;
            }
            case ']': {
                if(arr.pop() !== '[') return false
                break;
            }
        }
    }
    return !arr.length
};

第二种是维护一个map对象：

哈希表map

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let map = {
        '(': ')',
        '{': '}',
        '[': ']'
    }
    let stack = [];
    let len = s.length;
    if(len%2 !== 0) return false
    for(let i of s) {
        if(i in map) {
            stack.push(i)
        }  else {
            if(i !== map[stack.pop()]) return false
        }
    }
    return !stack.length
};