力扣-[简单]20. 有效的括号

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

有效字符串需满足：

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

 示例 1：
 输入：s = "()"
 输出：true

 示例 2：
 输入：s = "()[]{}"
 输出：true
 示例 3：

 输入：s = "(]"
 输出：false
 示例 4：

 输入：s = "([)]"
 输出：false
 示例 5：

 输入：s = "{[]}"
 输出：true

题解:

一打眼 , 这肯定是要用栈的.

自己的解法:

思路很直接

如果是左边入栈 , 如果是右边 , 出栈匹配.
最后判断下栈是不是空了.

 public boolean isValid(String s) {
        if(s == null || s.length() <= 0){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for(int i = 0,len = s.length(); i< len; i++){
            char c = s.charAt(i);
            boolean left = isLeft(c);
            if(i == 00 && ! left){
                return false;
            }
            if(left){
                stack.push(c);
            }else{
                if(stack.size() <= 0 || !isPair(stack.pop().charValue(),c)){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
    public boolean isLeft(char ch){
        return ch == '(' || ch == '{' || ch == '[';
    }
    public boolean isPair(char c , char c2){
        return (c == '(' && c2 == ')') ||(c == '{' && c2 == '}') ||(c == '[' && c2 == ']');
    }

取巧一点

如果是左边 , 把右边的入栈 , 如果是右边 , 出栈匹配一下.

效率是高了, 但是我学得阅读性差了点 .

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i=0;i<s.length();i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || c != stack.pop()){
                return false;
            }
        }
        return stack.isEmpty();
    }

再高效一点

遍历玩了一个数组 , 等于手动做了一个[指针]的栈.

其实我自己也想到了这个方式, 但我觉得可以性能不好 . 必然是用栈性能好.

唉... 太年轻..

 public boolean isValid(String s) {
        int len = s.length();
        if (len%2 == 1) {
            return false;
        }
        char[] stack = new char[len];
        int index = 0;
        for (char c : s.toCharArray()) {
            if (index == 0) {
                if (c == '(' || c == '[' || c == '{') {
                    stack[index++] = c;
                } else {
                    return false;
                }
            } else {
                if (c == ')' && '(' == stack[index - 1]) {
                    index--;
                } else if (c == ']' && '[' == stack[index - 1]) {
                    index--;
                } else if (c == '}' && '{' == stack[index - 1]) {
                    index--;
                } else {
                    stack[index++] = c;
                }
            } 
        }
        return index == 0;
    }