2
\$\begingroup\$

How can I optimize this algorithm to reverse strings inside parentheses?

String reverseParentheses(String s) {
    String tmpCh = new String("");
    String tmpChRe = new String("");
    String tmp = new String("");
    int l = s.length();
    int n = 0;
    int j =0;
    for(int i = 0;i<l;i++){
            if(s.charAt(i)=='(')
                    n++;
    }
    int T[] = new int[n];
    for(int i=0;i<l;i++){
            if(s.charAt(i)=='('){
                    T[j]=i;
                    j++;
            }
    }
    j=0;
    while(n>0){
            j = T[n-1] + 1;
            while(s.charAt(j)!=')'){
                    tmpCh = tmpCh + s.charAt(j);
                    j++;
            }
            for(int q=tmpCh.length()-1;q>=0;q--)
                    tmpChRe = tmpChRe + tmpCh.charAt(q);
            tmp = s.substring(0,T[n-1]) + tmpChRe + s.substring(T[n-1]+tmpChRe.length()+2);
            s = tmp;
            n--;
            tmp = "";
            tmpCh = "";
            tmpChRe = "";
    }
    return s ;
}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ @dhiareznov as in any examples? :) \$\endgroup\$
    – h.j.k.
    Mar 6 '17 at 13:39
  • \$\begingroup\$ @h.j.k. let's take "abc(de)fgh" as an input , the output is "abcedfgh" \$\endgroup\$ Mar 7 '17 at 19:35
3
\$\begingroup\$

I consider your solution to be hard to read, and also inefficient.

Readability

String tmpCh = new String("");
String tmpChRe = new String("");
String tmp = new String("");
int l = s.length();
int n = 0;
int j =0;

Of the six variables declared at the top, the only one whose meaning is obvious is l — and since you use l in only one place, I wouldn't even bother making a variable for it.

Your variable naming is problematic. "tmp" is always meaningless as part of a local variable name; local variables are always, by definition, temporary. Furthermore, a better way to indicate the temporary nature of these variables is to place them in the proper scope. Instead of resetting them to empty strings at the end of your while(n>0) loop, declare and initialize them at the top of the loop, so that they are properly scoped:

// Useless assignment.  It gets reassigned right away inside the loop.
// j = 0;

// You only ever use n-1, then n is decremented at the end of the loop.
// So you might as well decrement it right away.
while (n-- > 0) {
    // Formerly j
    int parenStart = T[n] + 1;
    int parenEnd = s.indexOf(')', parenStart);

    // Formerly tmpCh
    String contents = s.substring(parenStart, parenEnd);

    // No need for tmpChRe.  No need for tmp.
    s = s.substring(0, T[n]) +
        new StringBuilder(contents).reverse() +
        s.substring(T[n] + contents.length() + 2);
}
return s;

Please put some spaces here:

for(int i=0;i<l;i++){

This would be more conventional and easier to read:

for (int i = 0; i < l; i++) {

Efficiency

Strings in Java are immutable. Any time you concatenate strings using a + b, the compiler actually writes new StringBuilder(a).append(b).toString();. That creates a lot of garbage, and it also involves copying the entire contents of both strings. So, when you loops like this, which work build strings one character at a time, are hugely inefficient!

while(s.charAt(j)!=')'){
        tmpCh = tmpCh + s.charAt(j);
        j++;
}
for(int q=tmpCh.length()-1;q>=0;q--)
        tmpChRe = tmpChRe + tmpCh.charAt(q);

If you need to build a string by repeatedly appending characters, create one StringBuilder and append to it. Note that StringBuilder also has a .reverse() method that would be helpful.

Suggested solution

This solution performs all of the manipulation within one char[] array, so there is hardly any new memory allocated. It also validates that the input string's parentheses are properly matched; your code would either ignore mismatches or crash with an ArrayIndexOutOfBoundsException.

public static String reverseParentheses(String s) {
    char[] chars = s.toCharArray();
    int[] openPosStack = new int[chars.length];
    int openPosTop = -1;

    for (int i = 0; i < chars.length; i++) {
        switch (chars[i]) {
          case '(':
            // Push the index of the open parenthesis onto the stack
            openPosStack[++openPosTop] = i;
            break;
          case ')':
            // Reverse substring from the matching open parenthesis to here
            if (openPosTop < 0) {
                throw new IllegalArgumentException("Parenthesis mismatch");
            }
            int a, b;
            for (a = openPosStack[openPosTop--], b = i; a < b; a++, b--) {
                char swap = chars[a];
                chars[a] = chars[b];
                chars[b] = swap;
            }
        }
    }
    if (openPosTop >= 0) {
        throw new IllegalArgumentException("Parenthesis mismatch");
    }

    // Remove parentheses from output
    int o = 0;
    for (int i = 0; i < chars.length; i++) {
        switch (chars[i]) {
          case '(': case ')':
            break;
          default:
            chars[o++] = chars[i];
        }
    }
    return new String(chars, 0, o);
}
\$\endgroup\$
4
  • \$\begingroup\$ Very clear solution indeed, can you please write the algorithm you used? I would prefer you write some kind of comment on top of the method. Why you chose to remove parenthesis in another pass? \$\endgroup\$
    – CodeYogi
    Sep 25 '17 at 20:43
  • \$\begingroup\$ reverseInsideParentheses seem more accurate. \$\endgroup\$
    – CodeYogi
    Sep 25 '17 at 20:44
  • \$\begingroup\$ @CodeYogi You could try to remove the parentheses at the same time as the reversal is being done, but the bookkeeping would get very nasty. \$\endgroup\$ Sep 25 '17 at 20:50
  • \$\begingroup\$ I am too naive for this but I feel strongly that method is too long and doing too much. \$\endgroup\$
    – CodeYogi
    Sep 25 '17 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.