20. 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例?2：

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

示例?3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s?仅由括号?'()[]{}'?组成

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

方法2：

    public boolean isValid(String s) {
          if ((s.length() & 1) != 0 || s.length() == 1) {
            return false;
        }
        int max = s.length() / 2;
        char[] chars = new char[max];
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ('(' == c || '[' == c || '{' == c) {
                if (index >= max) {
                    return false;
                }
                chars[index] = c;
                index++;
            } else if (index-- > 0) {
                char aChar = chars[index];
                if (')' == c) {
                    if (aChar != '(') {
                        return false;
                    }
                } else if (']' == c) {
                    if (aChar != '[') {
                        return false;
                    }
                } else if ('}' == c) {
                    if (aChar != '{') {
                        return false;
                    }
                }
            } else {
                return false;
            }
        }
        return index==0;
    }

方法3：

    public boolean isValid(String s) {
        char[] l = {'(','[','{'};
        char[] r = {')',']','}'};
        char[] ss = s.toCharArray();
        int n = ss.length;
        char[] st = new char[10010];
        int top = -1;
        st[++top] = ss[0];
        boolean flag = true;
        for(int i = 1; i < n; i++)
        {
            char c = ss[i];
            if(c == '(' || c == '[' || c == '{')
                st[++top] = c;
            else
            {
                if(top < 0)
                {
                    flag = false;
                    break;
                }
                if(c == ')' && st[top] != '(')
                {
                    flag = false;
                    break;
                }
                if(c == ']' && st[top] != '[')
                {
                    flag = false;
                    break;
                }
                if(c == '}' && st[top] != '{')
                {
                    flag = false;
                    break;
                }
                top--;
            }
        }
        if(top >= 0)
            flag = false;
        return flag;
    }