每天一题LeetCode【第17天】

T20. Valid Parentheses【Easy】

题目

给定一个只包含字符'（'，'）'，'{'，'}'，'['和']'的字符串，确定输入字符串是否是有效的。

括号必须正确匹配，比如“（）”和“（）[] {}”都有效，但“（]”和“（[]]”不是。
例如，

   给出链表: 1->2->3->4->5,以及 n = 2.

   在移除了倒数第二个节点后, 链表变成了 1->2->3->5.

补充：

给出的 n 总是有效地

尝试把这题一遍过

思路

① 首先建议了解一下栈（先进后出的数据结构，类比桶装容器）

② 把识别左边的括号把对应的右边的括号放入栈中

③ 没有左边了以后从栈中 pop 出括号和下一子比较是否相同，若不相同或者栈空了代表错了

④ 总的思想就是 ② ③ 两步的操作，具体看代码就好~

⑤ 有问题欢迎吐槽~

代码

代码取自 Top Solution，稍作注释

 public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (char c : s.toCharArray()) {
       // 把识别左边的括号把对应的右边的括号放入栈中
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        //没有左边了以后从栈中 pop 出括号和下一子比较是否相同，若不相同或者栈空了代表错了
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    //如果一直没错并且栈空了就代表是有效的
    return stack.isEmpty();
    }

补充

这种括号匹配的题一般的通常想法就是栈吧（这算什么补充）~