Share my Java BFS solution


  • 287

    The idea is straightforward, with the input string s, we generate all possible states by removing one ( or ), check if they are valid, if found valid ones on the current level, put them to the final result list and we are done, otherwise, add them to a queue and carry on to the next level.

    The good thing of using BFS is that we can guarantee the number of parentheses that need to be removed is minimal, also no recursion call is needed in BFS.

    Thanks to @peisi, we don't need stack to check valid parentheses.

    Time complexity:

    In BFS we handle the states level by level, in the worst case, we need to handle all the levels, we can analyze the time complexity level by level and add them up to get the final complexity.

    On the first level, there's only one string which is the input string s, let's say the length of it is n, to check whether it's valid, we need O(n) time. On the second level, we remove one ( or ) from the first level, so there are C(n, n-1) new strings, each of them has n-1 characters, and for each string, we need to check whether it's valid or not, thus the total time complexity on this level is (n-1) x C(n, n-1). Come to the third level, total time complexity is (n-2) x C(n, n-2), so on and so forth...

    Finally we have this formula:

    T(n) = n x C(n, n) + (n-1) x C(n, n-1) + ... + 1 x C(n, 1) = n x 2^(n-1).

    Following is the Java solution:

    public class Solution {
        public List<String> removeInvalidParentheses(String s) {
          List<String> res = new ArrayList<>();
          
          // sanity check
          if (s == null) return res;
          
          Set<String> visited = new HashSet<>();
          Queue<String> queue = new LinkedList<>();
          
          // initialize
          queue.add(s);
          visited.add(s);
          
          boolean found = false;
          
          while (!queue.isEmpty()) {
            s = queue.poll();
            
            if (isValid(s)) {
              // found an answer, add to the result
              res.add(s);
              found = true;
            }
          
            if (found) continue;
          
            // generate all possible states
            for (int i = 0; i < s.length(); i++) {
              // we only try to remove left or right paren
              if (s.charAt(i) != '(' && s.charAt(i) != ')') continue;
            
              String t = s.substring(0, i) + s.substring(i + 1);
            
              if (!visited.contains(t)) {
                // for each state, if it's not visited, add it to the queue
                queue.add(t);
                visited.add(t);
              }
            }
          }
          
          return res;
        }
        
        // helper function checks if string s contains valid parantheses
        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;
        }
    }
    

  • 0
    H

    Greetings. I think your solution is really awesome. The usage of "visited set" speeds up the program a lot especially when dealing with large test cases


  • 5

    I guess that's the beauty of BFS. I love this problem btw!


  • 11

    I think the isValid function you don't need a stack for it.

    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 == ')') {
                if (count == 0) return false;
                count--;
            }
        }
        return count == 0;
    }

  • 0

    Even better! Thanks peisi!


  • 0

    too much python this 2 monthes, i almost forgot how to write java .....


  • 8

    And another improvement is you can add the index of the removal to the queue also.
    That is instead of add the new string s you add a tuple (s, i)
    Then when you generate the strings for the next level, you start from the index you polled.
    This can save you 50% of time.


  • 14
    I
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.remove();
                // Valid
                if (isValid(cur)) {
                    reached = true;
                    res.add(cur);
                }
                // Not Valid Then Delete 
                if (!reached) {
                    for (int j = 0; j < cur.length(); j++) {
                        if (cur.charAt(j) != '(' && cur.charAt(j) != ')') continue;
                        String newStr = cur.substring(0, j) + cur.substring(j + 1);
                        if (!visited.contains(newStr)) {
                            queue.add(newStr);
                            visited.add(newStr);
                        }
                    }
                }
            }
            if (reached) break;
        }
    

    Great idea! I think it is more clear if you can process all candidate strings with same length at one time.


  • 0

    Thanks iBella! When I do BFS, I like to use the null technique to help me control the levels, sometimes it's redundant (like in this problem), I have updated my code to make it even cleaner.


  • 0

    Hi peisi, could you post your solution here that uses the tuple thing? Thanks a lot!


  • 0

    ok. Umm..Let me see how to write it in java~


  • 9
    S

    Hi,I think there is something wrong with your answer.
    Whenever you got a solution,you should store the length of this solution.
    And after that, when you get a string from your queue, if the length of it is smaller than the length of the solution, you should immediately break the while loop.
    ex. input="()(()"
    Your code will get the answer ["()()","()",""] if you don't set the length of solution to be 4 when you get "()()".
    By the way,can you analysis the running time of your code?Thanks


  • 0
    I
    This post is deleted!

  • 1

    OK, i posted my solution. By using this additional information, we can avoid generate duplicate strings all together. It runs 16 ms without the Set.

    i didn't find a nice way to use tuple in java and I used a inner class for it.

    https://leetcode.com/discuss/67908/java-bfs-solution-16ms-avoid-generating-duplicate-strings


  • 0
    H

    In java, you can use an array with len 2 to represent a tuple of size 2


  • 0
    D

    the valid checking method is really smart


  • 35

    @SenyangZ Hi, there is no such problem with this code. It actually generates only ["()()"] on the given input "()(()". You may find it weird since the code does not explicitly record the maximum length of the valid parentheses.

    However, it does it implicitly. For a string of parentheses to be valid, its number of parentheses should be even. And at any time, strings in queue will only differ in length of 1 (this is the implicit control). When we find "()()" to be valid, both "()" and "" have not been added to queue yet and all the shorter strings are of length of 3, which must be invalid.


  • 0
    L

    @ jianchao.li.fighter, thanks, you are right!


  • 0

    Thank you @jianchao.li.fighter! I love your explanation!


  • 0

    Yes we can. But in the end i found defining a Tuple class maybe better for readability.
    And now it down to 16 ms with a 3-tuple.


Log in to reply
 

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