O(n) Solution in Java


  • 1
    X

    Solution
    By implementing a simple stack the problem can be solved in a single pass. As we iterate over the characters in the string we push the opposite bracket onto the stack to allow for a simplified checking process when it comes time to pop values off.

    After iterating through all values we return a function that will be true if our stack is empty meaning all parenthesis have been closed or false if there's still parenthesis left over.

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

    Complexity Analysis

    • Time Complexity: O(n) We traverse the string containing n characters only once, and each stack operation costs only O(1) time.
    • Space Complexity: O(n) The extra space will depend on the number of unmatched parenthesis stored in the stack at once. In a worst case scenario this will be n elements.

  • 0
    W

    Minor improvements :)

    public boolean isValid(String s) {
            Stack<Character> open = new Stack<>();
            HashMap<Character, Character> map = new HashMap<>();
            map.put('(', ')');
            map.put('[', ']');
            map.put('{', '}');
            for (char x : s.toCharArray()) {
                if (map.containsKey(x)) {
                    open.push(x);
                } else if (open.isEmpty() || 
                                    map.get(open.pop()) != x) {
                    return false; 
                }
            }
            return open.isEmpty();
        }
    

Log in to reply
 

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