LeetCode - 有效的括号

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

Related Topics

• 栈

• 字符串

•  2695

•  0

分析

1. 字符串的长度必须可以被 2 整除

2. 六个字符的ASCII码 相匹配的两个字符对应数字之差为 1 或者 2

   左括号	数字	右括号	数字
   {	123	}	125
   [	91	]	93
   (	28	)	29

1. 在map中按照对应的键值 存放
2. 利用栈 的特性来处理 ： 如果当前栈顶元素和下一个需要匹配的括号，刚好是一对，则通过，否则，直接返回false

public boolean isValid(String s) {
    //字符串的数量必须是双数
    if (s.length() % 2 != 0) return false;
    Map map = new HashMap(){{
        put('(', ')');
        put('{', '}');
        put('[', ']');
    }};
    Stack stack = new Stack<>();
    for (Character c : s.toCharArray()) {
        if (map.containsKey(c)){
            //如果当前字符是左边字符，入栈
            stack.push(c);
        }else {
            
            if ((!stack.isEmpty()) && map.get(stack.peek()).equals(c)){
                stack.pop();
            }else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

public boolean isValid2(String s) {
    //字符串的数量必须是双数
    if (s.length() % 2 != 0) return false;
    Stack stack = new Stack<>();
    for (Character c : s.toCharArray()) {
        if (!stack.isEmpty()){
            if ((c - stack.peek() == 1 || c - stack.peek() == 2)) {
                stack.pop();
                continue;
            }
        }
        stack.push(c);
    }
    return stack.isEmpty();
}

直接使用判断 栈顶元素 和当前 元素 是否是 匹配的， 如果不匹配，直接返回false

public boolean isValid(String s) {
    //字符串的数量必须是双数
    if (s.length() % 2 != 0) return false;
    Stack stack = new Stack<>();
    Character pop;
    for (Character c : s.toCharArray()) {
        if (c == '{' || c == '[' || c== '('){
            stack.push(c);
        }else {
            if (stack.isEmpty()) return false;
            //取出栈顶元素
            pop = stack.pop();
            if (pop == '{' && c != '}') return false;
            if (pop == '[' && c != ']') return false;
            if (pop == '(' && c != ')') return false;
        }
    }
    return stack.isEmpty();
}

利用数组来模拟栈

运行时长最短

public boolean isValid(String s) {
    int n=s.length();
    char[] stack=new char[n+1];
    int top=-1;
    for(char c:s.toCharArray()){
        //栈为空或栈顶元素无法出栈
        if(top==-1||c=='('||c=='{'||c=='['){
            stack[++top]=c;
            //System.out.println("栈顶为"+top+",入栈"+c);
        }else{
            //System.out.println("栈顶为"+top+","+stack[top]+",可能出栈"+c);
            switch (c){
                case ')':
                    if(stack[top]=='('){
                        //System.out.println("出栈");
                        top--;
                    }else{
                        stack[++top]=c;
                    }
                    break;
                case ']':
                    if(stack[top]=='['){
                        //System.out.println("出栈");
                        top--;
                    }else{
                        stack[++top]=c;
                    }
                    break;
                case '}':
                    if(stack[top]=='{'){
                        //System.out.println("出栈");
                        top--;
                    }else{
                        stack[++top]=c;
                    }
                    break;
            }
        }
    }
    //System.out.println(top);
    return top==-1;
}