Simple Solution in Java


  • 0
    T

    The idea is put all the opening parentheses into the queue(stack) in order, then whenever we encounter a closing parentheses, we pop the top of the queue to see if that opening parentheses matches the closing one.
    If it doesn't match, then it's not valid.

    At the end, the queue should be empty. Else it's not valid.

    class Solution {
        private static Map<Character, Character> matchMap = new HashMap<>(3);
        static {
            matchMap.put(')', '(');
            matchMap.put('}', '{');
            matchMap.put(']', '[');        
        }
        
        public boolean isValid(String s) {
            Deque<Character> queue = new ArrayDeque<>(s.length() / 2);
            
            for(int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                Character matchC = matchMap.get(c);
                if(matchC == null) {
                    queue.offerFirst(c);
                } else {
                    Character top = queue.pollFirst();
                    if(!matchC.equals(top)){
                        return false;
                    }
                }
            }
            
            return queue.isEmpty();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.