Stack

Java里尽量避免使用Stack class

• Stack class in Java uses synchronized methods since it is a subclass of Vector.

• A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

   Deque<Integer> stack = new ArrayDeque<Integer>();

Minimum Remove to Make Valid Parentheses

• Stack + Set solution, 2 pass

• first pass

  • Stack to store index of pendingLeft

  • Set to store index of unpaired right bracket

  • move element from stack to set

• then second pass:

  • if set.contains(curIdx), then skip it/don't append it

• O(N) Time , O(N) space

public String minRemoveToMakeValid(String s) {
        int len = s.length();
        Stack<Integer> pendingLeft = new Stack<>();
        Set<Integer> unpairedright = new HashSet<>();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                pendingLeft.add(i);
            } else if (c == ')') {
                if (pendingLeft.isEmpty()) {
                    unpairedright.add(i);
                } else {
                    pendingLeft.pop();
                }
            }
        }
        while (!pendingLeft.isEmpty()) {
            unpairedright.add(pendingLeft.pop());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            if (unpairedright.contains(i)) continue;
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }

• 这题还有O(1) space solution, 不用Stack, Set

• 需要记录两个变量，pendingRight和unpairedLeft

• 先scan 一遍记录pendingRight cnt

• 然后再scan, 每次遇到一个left bracket, 则unpairedLeft++

• 比较tricky, 感觉面试时应该不要求优化到O(1)吧

public String minRemoveToMakeValid(String s) {
        int len = s.length();
        int pendingRight = 0;
        for (int i = 0; i < len; i++){
            if (s.charAt(i) == ')') pendingRight++;
        }
        StringBuilder sb = new StringBuilder();
        int unpairedLeft = 0;
        for (int i = 0;i < len; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                if (unpairedLeft == pendingRight) continue; // no more pendingRight to be paired with current left
                unpairedLeft++;
            } else if (c == ')') {
                //try to pair with unpairedLeft
                pendingRight--;
                if (unpairedLeft == 0) continue; //no more unpairedLeft remaining, so need to skip current right
                unpairedLeft--;
            } 
            sb.append(c);
        }
        return sb.toString();
    }