Clean Java Solution


  • 0
    H
    /**
    Constraints
        s can be null or empty
        
    Tests
        null -> false
        "" -> false
        "{}" -> true
        "]" -> false
        "(" -> false
        "({[][]})" -> true
        
    Ideas
        push char in a stack, when a enclosing tag is found, looks for opening tag on stack peak
        if not found, return invalid
            time complexity -> o(n)
            space complexity -> o(n)
    */
    class Solution {
        public boolean isValid(String s) {
            if(s == null || s.length() == 0) return false;
            Deque<Character> stack = new ArrayDeque<>();
            for(int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(isEnclosingTag(c)) {
                    if(stack.isEmpty()) return false;
                    char o = stack.pop();
                    if(!isOpeningTagOf(o, c)) return false;
                } else {
                    stack.push(c);
                }
            }
            return stack.isEmpty();
        }
        
        private boolean isEnclosingTag(char c) {
            return c == ']' || c == ')' || c == '}';
        }
        
        private boolean isOpeningTagOf(char o, char c) {
            if(c == ']') return o == '[';
            if(c == ')') return o == '(';
            if(c == '}') return o == '{';
            return false;
        }
    }
    

Log in to reply
 

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