20. Valid Parentheses

题目

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

有效字符串需满足:

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

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

示例1:

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

示例2:

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

示例3:

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

示例4:

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

示例5

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

解法

解法一:

借助栈。如果是左半部分的括号,即(,{,或[,入栈,如果是右半部分的括号,再判断栈顶是不是其对应的左半部分括号,是的话,就弹出栈顶,否则,则不是合法的括号

Java

    public boolean isValid(String s) {
        Stack<Character> sc = new Stack<>();
        int len = s.length();
        for(int i = 0 ; i < len ; i ++) {
            if(s.charAt(i) == '('|| s.charAt(i) == '{'|| s.charAt(i) == '[') {
                sc.push(s.charAt(i));
            } else if(sc.empty()) {
                return false;
            } else if(s.charAt(i) == ')') {
                if(sc.peek() == '(') {
                    sc.pop();
                } else {
                    return false;
                }
            } else if(s.charAt(i) == '}') {
                if(sc.peek() == '{') {
                    sc.pop();
                } else {
                    return false;
                }
            } else if(s.charAt(i) == ']') { 
                if(sc.peek() == '[') {
                    sc.pop();
                } else {
                    return false;
                }
            }
        }
        return sc.empty();
    }
};

解法二:

利用字符串替换函数,如果字符串是合法的,那么,将合法的括号对替换为空字符串之后,最后的字符串长度一定为0.

Java

1
2
3
4
5
6
7
public boolean isValid(String s) {
int length = s.length();
for (int i = 0;i < length;i++) {
s = s.replace("{}", "").replace("[]", "").replace("()", "");
}
return 0 == s.length();
}
0%