Check the expression has valid or Balanced parenthesis or not

The problem, simply

You get a string made only of the brackets ( ) [ ] { }. Say true if it is balanced and false if not.

Balanced means three things:

• Every closing bracket has an opening bracket of the same kind.
• They close in the right order: the one opened last is closed first.
• Nothing is left open at the end.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look for pairs sitting right next to each other, like (), [] or {}, and erase them. Erasing a pair can make a new pair touch, so keep going until nothing changes. If the string ends up empty, it was balanced.

1. Replace every (), [] and {} with nothing.
2. If the string changed, do it again.
3. Return whether the string is now empty.

class Solution {
    public boolean isValid(String s) {
        String before = null;
        while (!s.equals(before)) {          // stop when nothing changes
            before = s;
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        }
        return s.isEmpty();
    }
}

How long it takes: each round reads the whole string, and a deep nest like ((((())))) needs about n / 2 rounds, so O(n^2). Extra room: new strings are made each round, O(n).

Way 2: the clever way

Keep a pile of the brackets that are still open, a stack.

1. Read the string left to right.
2. An opening bracket goes on top of the pile.
3. A closing bracket must match the top of the pile. If the pile is empty or the top is a different kind, return false. Otherwise pop the top.
4. At the end, return true only if the pile is empty.

class Solution {
    public boolean isValid(String s) {
        Deque<Character> pile = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                pile.push(c);                          // a box is opened
            } else {
                if (pile.isEmpty()) return false;      // a lid with no box
                char open = pile.pop();
                if (c == ')' && open != '(') return false;
                if (c == ']' && open != '[') return false;
                if (c == '}' && open != '{') return false;
            }
        }
        return pile.isEmpty();                         // nothing left open
    }
}

How long it takes: each character is pushed or popped at most once, O(n). Extra room: the pile can hold up to n brackets, as in ((((((, so O(n).

Watch out for

• A closing bracket when the pile is empty, as in )(. Check before you pop, or pop() throws.
• Counting brackets is not enough. ([)] has the right counts and is still wrong.
• An odd length string can never be balanced. You can return false right away as a quick shortcut.
• Prefer ArrayDeque to Stack in Java. It is faster and is the recommended choice.

What interviewers ask next

• Only one kind of bracket, ( and ). You do not need a stack, only a counter. Add one for (, subtract one for ), fail if it goes below zero, and check it ends at zero. That is O(1) extra room.
• Fewest brackets to remove to make it valid. Use the stack to mark unmatched positions, then remove those. That is LeetCode 1249.
• Fewest brackets to add. Count unmatched ) while scanning, plus whatever is left open at the end.
• Longest valid substring. Push indices instead of characters, and keep the index of the last unmatched position at the bottom of the stack.
• What if there are other characters, like a+(b*c)? Skip anything that is not a bracket. The rest is the same.

Remember this

Grown-up words: the pile of open boxes is a stack, last opened first closed is LIFO, matching lids is bracket matching, and the boxes inside boxes are nested scopes.