Java BFS solution 16ms avoid generating duplicate strings


  • 26

    The naive BFS solution is quite simple to implement. To speed up we can use a Set to record all the strings generated and avoid revisit. But a better and faster solution is to avoid generate duplicate strings all together.

    The first observation is when we want to remove a ')' or '(' from several consecutive ones we only remove the first one, because remove any one the result will be the same. For example

    "())" ---> "()"
    only remove the first one of '))'
    

    The second observation is when we remove a character it must behind it's parent removal position. For example

    we need remove 2 from "(())(("
    we want to remove positions combination i,j with no duplicate
    so we let i < j then it will not generate duplicate combinations
    in practice, we record the position i and put it in to queue
    which is then polled out and used as the starting point of the next removal
    

    A third observation is if the previous step we removed a "(", we should never remove a ")" in the following steps. This is obvious since otherwise we could just save these two removals and still be valid with less removals. With this observation all the possible removals will be something like this

    ")))))))))((((((((("
    

    All the removed characters forming a string with consecutive left bracket followed by consecutive right bracket.

    By applying these restrictions, we can avoid generate duplicate strings and the need of a set which saves a lot of space.

    Ultimately we can further improve the algorithm to eliminate isValid calls. To do this we need to remove and only remove those characters that would lead us to valid strings. This needs some preprocess and can reduce the time to around 3ms.

    public List<String> removeInvalidParentheses(String s) {
        if (isValid(s))
            return Collections.singletonList(s);
        List<String> ans = new ArrayList<>();
        //The queue only contains invalid middle steps
        Queue<Tuple> queue = new LinkedList<>();
        //The 3-Tuple is (string, startIndex, lastRemovedChar)
        queue.add(new Tuple(s, 0, ')'));
        while (!queue.isEmpty()) {
            Tuple x = queue.poll();
            //Observation 2, start from last removal position
            for (int i = x.start; i < x.string.length(); ++i) {
                char ch = x.string.charAt(i);
                //Not parentheses
                if (ch != '(' && ch != ')') continue;
                //Observation 1, do not repeatedly remove from consecutive ones
                if (i != x.start && x.string.charAt(i - 1) == ch) continue;
                //Observation 3, do not remove a pair of valid parentheses
                if (x.removed == '(' && ch == ')') continue;
                String t = x.string.substring(0, i) + x.string.substring(i + 1);
                //Check isValid before add
                if (isValid(t))
                    ans.add(t);
                //Avoid adding leaf level strings
                else if (ans.isEmpty())
                    queue.add(new Tuple(t, i, ch));
            }
        }
        return ans;
    }
    
    public static boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(') ++count;
            if (c == ')' && count-- == 0) return false;
        }
        return count == 0;
    }
    
    private class Tuple {
        public final String string;
        public final int start;
        public final char removed;
    
        public Tuple(String string, int start, char removed) {
            this.string = string;
            this.start = start;
            this.removed = removed;
        }
    }
    //  125 / 125 test cases passed.
    //  Status: Accepted
    //  Runtime: 16 ms

  • 1
    L

    Thanks for your solution! What's the running time of your solution? Is it O(n!)?


  • 0
    H

    @dietpepsi

    else if (ans.isEmpty())
                    queue.add(new Tuple(t, i, ch));
    

    I understand you try to stop adding tuples into queue once you found valid one. But what if you add some Tuples already before you find a valid one? This could lead to add some next level(which is not minimum removals) valid ones into results, right?


Log in to reply
 

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