【Hot100】20. 有效的括号

20. 有效的括号

• 使用map

	private static final Map<Character,Character> map = new HashMap<Character,Character>(){
    {
    
        put('{','}'); put('[',']'); put('(',')'); put('?','?');
    }};
	public boolean isValid(String s) {
    
        if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        LinkedList<Character> stack = new LinkedList<Character>() {
    {
     add('?'); }};
        for(Character c : s.toCharArray()){
    
            if(map.containsKey(c)) stack.addLast(c);
            else if(map.get(stack.removeLast()) != c) return false;
        }
        return stack.size() == 1;
	}

• 不使用map，用栈

class Solution {
    
    public boolean isValid(String s) {
    
        if(s.isEmpty()){
    
            return true;
        }
            
        Stack<Character> stack=new Stack<>();
        for(char c:s.toCharArray()){
    
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.empty()||c!=stack.pop())
                return false;
        }
        return stack.empty();

    }
}

• 双队列

class Solution {
    
    public boolean isValid(String s) {
    
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
    
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
    
                deque.push(')');
            }else if (ch == '{') {
    
                deque.push('}');
            }else if (ch == '[') {
    
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
    
                return false;
            }else {
    //如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }
}

在迭代过程中，提前发现不符合的括号并且返回，提升算法效率。