leetcode20有效的括号（String）

发表于 | 分类于

题目

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

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。

示例1

1
2
输入: "()"
输出: true

示例2

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

示例3

1
2
输入: "(]"
输出: false

示例4

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

示例5

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

题解

这种匹配或者回文的题目一般都会用到栈，因为栈的特性就是：先进后出。相当于回文的效果。
我们碰到’(‘，栈push进去’)’；碰到’[‘，栈push进去’]’；碰到’(‘栈push进去’)’。这样当碰到右类型的括号时就出栈比较是否相等，如果不相等就直接返回false，相等则循环继续。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isValid(String s) {
        if(s==null||s.length()==0) return true;
        Stack<Character> stack = new Stack<>();
        for (Character ch:s.toCharArray()){
            if (ch=='('){
                stack.push(')');
            }else if (ch=='['){
                stack.push(']');
            }else if (ch=='{'){
                stack.push('}');
            }else {
                if (stack.isEmpty()||stack.pop()!=ch){//stack为空对应的第一个字符为右类型的括号；
                    return false;
                }
            }
        }
        return stack.isEmpty();//如果括号刚好匹配那么栈为空的，还有一个情况是只有一个左类型的括号，stack会push一个右类型的括号，然后跳出循环到这里，此时栈不为空，返回false
    }
}