【Hot100】20. Valid parentheses

20. Valid parenthesis

• Use 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;
	}

• Don't use map, With the stack

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

    }
}

• Double queue

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);
            // Touching the left bracket , Put the corresponding right parenthesis on the stack 
            if (ch == '(') {
    
                deque.push(')');
            }else if (ch == '{') {
    
                deque.push('}');
            }else if (ch == '[') {
    
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
    
                return false;
            }else {
    // If it is a right parenthesis, judge whether it matches the top element of the stack 
                deque.pop();
            }
        }
        // Finally, determine whether the elements in the stack match 
        return deque.isEmpty();
    }
}

In the iteration process , Find inconsistent brackets in advance and return , Improve the efficiency of the algorithm .