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

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();
    }