原题描述

原题链接

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

有效字符串需满足：

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

示例 1：

输入：s = “()” 输出：true

示例 2：

输入：s = “()[]{}” 输出：true

示例 3：

输入：s = “(]” 输出：false

示例 4：

输入：s = “([)]” 输出：false

示例 5：

输入：s = “{[]}” 输出：true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

个人解法

Java

public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length, n;
        if (len<=1){
            return false;
        }
        Integer[] ints = new Integer[len];
        for (int i = 0; i < len; i++) {
            ints[i] = 0 + chars[i];
        }
        Stack<Integer> st = new Stack<Integer>();
        for (int i = 0; i < len; i++) {
            if (ints[i] == 40 || ints[i] == 91 || ints[i] == 123) {
                st.push(ints[i]);
            } else {
                if (st.empty()){
                    return false;
                }else {
                    n = st.pop();
                    if (n - ints[i] != -1 && n - ints[i] != -2) {
                        return false;
                    }
                }
            }
        }
        if (!st.empty()){
            return false;
        }
        return true;
    }

JavaScript

/*
 * @lc app=leetcode.cn id=20 lang=javascript
 *
 * [20] 有效的括号
 */
// @lc code=start
var check = function (stack, origin) {
    if (stack[stack.length - 1] === '(') {
        return origin === ')'
    } else if (stack[stack.length - 1] === '{') {
        return origin === '}';
    } else if (stack[stack.length - 1] === '[') {
        return origin === ']';
    }
}
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    const stack = [];
    stack.push(s[0]);
    for (let i = 1; i < s.length; i++) {
        if (check(stack, s[i])) {
            stack.pop();
        } else {
            stack.push(s[i]);
        }
    }
    return stack.length === 0;
};
// @lc code=end

更优解法

Java

public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c=='('||c=='['||c=='{'){stack.push(c);}
            else if(stack.isEmpty()||c==')'&&stack.pop()!='('||c==']'&&stack.pop()!='['||c=='}'&&stack.pop()!='{'){return false;}
        }
        return stack.isEmpty();
    }

JavaScript

更优解法链接

判断匹配 使用了 map

var isValid = function(s) {
    const n = s.length;
    if (n % 2 === 1) {
        return false;
    }
    const pairs = new Map([
        [')', '('],
        [']', '['],
        ['}', '{']
    ]);
    const stk = [];
    for (let ch of s){
        if (pairs.has(ch)) {
            if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
                return false;
            }
            stk.pop();
        } 
        else {
            stk.push(ch);
        }
    };
    return !stk.length;
};