Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The point to this question is to use a stack data structure to keep track of string validity. We want to iterate through string s one character at a time, while considering the following 2 cases:

    1. The character is an opening bracket - push onto stack regardless what type.
    2. The character is a closing bracket - pop element off stack, if possible, and check whether it matches the given character. Return false if stack is empty or if they don't match.

    At the end, return true if the stack is empty, meaning all brackets matched; return false if non-empty.

    Time Complexity
    The time complexity is O(n) where n is the length of input s, since we iterate through each character once.

    class Solution {
        public boolean isOpening(char c) {
            return c == '{' || c == '(' || c == '[';
        }
        
        public boolean areMatching(char a, char b) {
            return a == '{' && b == '}' ||
                   a == '(' && b == ')' ||
                   a == '[' && b == ']';
        }
        
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                
                // Case 1: Opening bracket
                if (isOpening(c)) {
                    stack.push(c);
                } 
                // Case 2: Closing bracket
                else {
                    if (stack.isEmpty()) return false;
                    char bracket = stack.pop();
                    if (!areMatching(bracket, c)) {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }
    

Log in to reply
 

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