Naive solution in java explained. Could someone help confirm the time complexity?


  • 0
    R

    Here is a naive brute force solution.
    I use a queue to keep track of every possible combination starting with the original string.
    For each string removed from the queue, I scan the string, keeping a count of the the parentheses.

    a) If at any point of time, the count becomes negative (i.e. count of closing brackets is greater), we know that a starting bracket needs to be removed from the prefix seen up til now. So we get all such combinations of corrected prefix, combined with the unseen suffix and put the result back into the queue. We can abandon processing the rest of this string.
    b) If the entire string gets processed without the count becoming negative, then we check whether the count is positive, i.e. (count opening brackets is higher). In this case we can simply invert and reverse the string and make a recursive call, and invert the results and push them back into the queue.
    c) If the entire string gets processed and the final count is zero, means we have a well-formed string. So add it into the final results (a set).

    public List<String> removeInvalidParentheses(String s) {
            char[] arr = s.toCharArray();
            
            
            Set<String> set = new HashSet<String>();
            Queue<String> q = new LinkedList<String>();
            q.add(s);
            
            while (!q.isEmpty()) {
                String cur = q.remove();
                int count = 0;
                for (int i=0;i<cur.length();i++) {
                    char c = cur.charAt(i);
                    if (c != '(' && c != ')')
                        continue;
                    if (c == '(')
                        count++;
                    if (c == ')')
                        count--;
                    if (count < 0) {
                        q.addAll(removeClosingBrace(cur.substring(0,i+1),cur.substring(i+1)));
                        break;
                    }
                }
                if (count < 0) continue;
                if (count > 0) {
                    for (String str : removeInvalidParentheses(invert(cur)))
                        q.add(invert(str));
                }
                if (count == 0) set.add(cur);
            }
            return new ArrayList<String>(set);
        }
        
        private String invert(String s) {
            s = new StringBuilder(s).reverse().toString();
            char[] inverted = new char[s.length()];
            int i = 0;
            for (char c : s.toCharArray()) {
                if (c == '(')
                    inverted[i++] = ')';
                else if (c == ')')
                    inverted[i++] = '(';
                else
                    inverted[i++] = c;
             }
             return new String(inverted);
        }
        
        private List<String> removeClosingBrace(String s, String suffix) {
            char[] arr = s.toCharArray();
            List<String> res = new ArrayList<String>();
            for (int i=0;i<arr.length;i++) {
                if (arr[i] == ')') {
                    while (i < arr.length && arr[i] == ')')
                        i++;
                    res.add(s.substring(0,i-1) + s.substring(i) + suffix);
                }
            }
            return res;
        }
    
    Can someone help confirm the time complexity of my code? I'm guessing that it's 2^n but not sure.

Log in to reply
 

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