来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses/

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

题目分析

栈：先进后出

思路：

• 字符串长度必定为偶数，若为奇数直接返回false（即括号无效）；
• 遍历字符串，遇到左括号放入栈；
• 遇到右括号时，取栈顶元素（空 or 左括号）比较。若为空，直接返回false，若为左括号判断与该右括号是否相同类型；
• 类型相同，继续遍历；类型不同，直接返回false

代码实现

public class Valid20 {

    public static void main(String[] args) {
        Valid20 valid20 = new Valid20();
        boolean result = valid20.isValid("()[]{}");
        System.out.println(result);
    }


    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * <p>
     * 有效字符串需满足：
     * <p>
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        int n = s.length();

        // 奇数不满足
        if (n % 2 != 0) {
            return false;
        }
        // 存放右括号
        Map<Character, Character> map = new HashMap<Character, Character>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');

        // 栈，先进后出，存放左括号
        LinkedList<Character> stack = new LinkedList<Character>();

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if(!map.containsKey(ch)){
                stack.addLast(ch);
            } else {
                if(stack.isEmpty() || stack.getLast() != map.get(ch)){
                    return false;
                }
                stack.removeLast();
            }

        }

        return stack.isEmpty();


    }


}

复杂度

• 时间复杂度：O(logn)，其中 n 是定版本的数量。
• 空间复杂度：O(1)，只需要常数的空间保存变量。

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！
�